两个操作, 区间增加和单点查询.
思路: 将整个数组按照 block(block=sqrt(n))分成许多小块, lump[i]表示点 i 所在的块, tag[i]表示编号为 i 的块的增加值, 如果是进行区间增加操作, 我们一般可以把区间 [l,r] 分成三个部分, 左边不完整的区间 (只含有某块中的部分点), 中间完整的区间(含有一些块的所有点), 右边不完整的区间. 这样对于左右的不完整区间, 他们的点的数量是比较少的, 我们可以进行暴力更新, 对于中间的完整区间, 一般来说他们的点比较多, 我们就用标记数组 tag[i] 来记录第 i 块里增加的数, 从而避免对太多的点进行单点更新. 在单点查询时, 某个点的值就是本身数组的值加上这个点所在的块的标记数组值(a[r]+tag[lump[r]).
点 i 所在的块是 lump[i]=(i-1)/block+1, 表示 lump[i]=i/block+1.
假设现在 n=9, 那么 block=sqrt(9)=3.
对 1 到 9 之间的点分块, 在 i=3 时, 错误: 3/3+1=2,3 就在第二组 , 但是这是不对的, 按理说 3 应该在第一组, 怎么办, 把 3 减 1....
代码:
- #include<iostream>
- #include<cstring>
- #include<algorithm>
- #include<queue>
- #include<map>
- #include<stack>
- #include<cmath>
- #include<vector>
- #include<set>
- #include<cstdio>
- #include<string>
- #include<deque>
- using namespace std;
- typedef long long LL;
- #define eps 1e-8
- #define INF 0x3f3f3f3f
- #define maxn 50005
- /*struct point{
- int u,w;
- };
- bool operator <(const point &s1,const point &s2)
- {
- if(s1.w!=s2.w)
- return s1.w>s2.w;
- else
- return s1.u>s2.u;
- }*/
- int tag[maxn],a[maxn],lump[maxn];
- int n,m,k,t,block;
- void add(int l,int r,int c)// 这里注意要把各个块的边界写正确
- {
- for(int i=l;i<=min(lump[l]*block,r);i++)// 左边的不完整的块 暴力更新每个点
- a[i]+=c;
- if(lump[l]!=lump[r])// 左边界和右边界不在一个块里面
- {
- for(int i=(lump[r]-1)*block+1;i<=r;i++)// 右边的不完整的块 暴力更新
- a[i]+=c;
- }
- for(int i=lump[l]+1;i<=lump[r]-1;i++)// 中间的完整的块的标记数组 增加值
- tag[i]+=c;
- }
- int main()
- {
- scanf("%d",&n);
- block=sqrt(n);
- fill(tag,tag+maxn-1,0);
- for(int i=1;i<=n;i++)// 给每个点分块
- lump[i]=(i-1)/block+1;
- for(int i=1;i<=n;i++)
- scanf("%d",&a[i]);
- int op,l,r,c;
- for(int i=1;i<=n;i++)
- {
- scanf("%d%d%d%d",&op,&l,&r,&c);
- if(op==0)
- add(l,r,c);
- else
- printf("%d\n",a[r]+tag[lump[r]]);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2788728.html