数列分块1

题目描述

给出一个长为  的数列，以及 n个操作，操作涉及区间加法，单点查值。

大家很容易会想到差分。但题目的单点查询是在线查询（修改操作和查询操作是穿插在一起的，立刻回答）而差分是离线的（全部打完标记后，再求前缀和。把所有修改操作全做完了，再全部回答）如果差分在线做的，复杂度很高，要不停求前缀和。

 

所以这就要用分块了！

分块：优雅的暴力

我们先把数列切成√n块，那每一块就是√n，一共是n块。a数组是原始数组，b数组是用来打标记的。

分块口诀：大段维护，小段暴力。

#include <bits/stdc++.h> using namespace std; typedef long long ll; ll read()//快读 { ll x=0,f=1; char ch=getchar(); while(!isdigit(ch)) { if(ch=='-') f=-1; ch=getchar(); } while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); } return x*f; } int n,blo; int v[50005],bl[50005],atag[50005]; void add(int a,int b,int c)//大段维护，小段暴力 { for(int i=a;i<=min(bl[a]*blo,b);i++)//左端点所在的右边界 bl[a]左端点所在的块号*块的大小 v[i]+=c;//暴力加法 if(bl[a]!=bl[b])//如果a块和b块不相同 for(int i=(bl[b]-1)*blo+1;i<=b;i++)//b所在的左端点到b v[i]+=c;//暴力加法 for(int i=bl[a]+1;i<=bl[b]-1;i++)//a、b之间的完整大块 atag[i]+=c;//打标记 } int main() { n=read(); blo=sqrt(n);//每一块大小√n for(int i=1;i<=n;i++) v[i]=read(); for(int i=1;i<=n;i++) bl[i]=(i-1)/blo+1;//元素属于哪一块 for(int i=1;i<=n;i++) { int f=read(),a=read(),b=read(),c=read();//一系列查询 a~b区间 if(f==0) add(a,b,c);//区间统一增加 if(f==1) printf("%d\n",v[b]+atag[bl[b]]);//单点查询 原来的值v[b]加上一系列打上的标记 } return 0; }

写作不易，麻烦动手点个赞，再走，行不？