给出一个长为n的数列,以及n个操作,操作涉及区间加法,区间求和。
这题的询问变成了区间上的询问,不完整的块还是暴力;而要想快速统计完整块的答案,需要维护每个块的元素和,先要预处理一下。
考虑区间修改操作,不完整的块直接改,顺便更新块的元素和;完整的块类似之前标记的做法,直接根据块的元素和所加的值计算元素和的增量。
更改后的区间加法
1 void interval_add(LL ll,LL rr,LL v)
2 {
3 for(LL i=ll;i<=min(where[ll]*m,rr);i++)
4 //这里判断的是where[ll]是不完全块的情况,也就是ll在他实际块最左端的右侧,
5 // 然后便利ll-所在块的结尾/rr,暴力增加
6 a[i]+=v,sum[where[ll]]+=v;
7 // 注意sum表示的是一个块内的元素和,where表示的是块的位置
8 if(where[ll]!=where[rr])
9 // 注意如果是ll和rr在一个块中的话,上面已经加过一边,所以不用加
10 {
11 for(LL i=(where[rr]-1)*m+1;i<=rr;i++)
12 // 这里判断的是rr在他实际所在块的最右端左侧的情况
13 // where[i]*m表示的是第i个块最右端的元素
14 // where[rr]-1就是rr所在块左边那个块最右端的元素
15 // 一直到rr暴力增加
16 a[i]+=v,sum[where[rr]]+=v;
17 }
18 for(LL i=where[ll]+1;i<=where[rr]-1;i++)
19 //这里where[ll]和where[rr]均已暴力处理过,所以只枚举中间的块就可以
20 add[i]+=v;
21 }
区间查询
1 void interval_ask(LL ll,LL rr)
2 {
3 LL ans=0;
4 for(LL i=ll;i<=min(where[ll]*m,rr);i++)
5 ans+=a[i]+add[where[i]];
6 // 暴力求和 ,注意where里面要写ll\i,因为我们始终是在ll到它的所在区间结尾的元素内循环
7 //
8 if(where[ll]!=where[rr])
9 for(LL i=(where[rr]-1)*m+1;i<=rr;i++)
10 //注意这里需要加一,因为所有的for都是<=,如果不写+1会加两边
11 ans+=a[i]+add[where[i]];
12
13 for(LL i=where[ll]+1;i<=where[rr]-1;i++)
14 ans+=sum[i]+add[i]*m;
15 // 这里要*区间内元素的个数
16
17 printf("%lld\n",ans);
18 }
完整代码
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #define LL long long
6 using namespace std;
7 const LL MAXN=100001;
8 LL n,q,m,how,l,r,v;
9 LL a[MAXN];// 初始值
10 LL add[MAXN];// 后来每个块上加入的值
11 LL where[MAXN];// 记录每一个值对应第几块
12 LL sum[MAXN];//记录每一块内的元素和
13 void interval_add(LL ll,LL rr,LL v)
14 {
15 for(LL i=ll;i<=min(where[ll]*m,rr);i++)
16 //这里判断的是where[ll]是不完全块的情况,也就是ll在他实际块最左端的右侧,
17 // 然后便利ll-所在块的结尾/rr,暴力增加
18 a[i]+=v,sum[where[ll]]+=v;
19 // 注意sum表示的是一个块内的元素和,where表示的是块的位置
20 if(where[ll]!=where[rr])
21 // 注意如果是ll和rr在一个块中的话,上面已经加过一边,所以不用加
22 {
23 for(LL i=(where[rr]-1)*m+1;i<=rr;i++)
24 // 这里判断的是rr在他实际所在块的最右端左侧的情况
25 // where[i]*m表示的是第i个块最右端的元素
26 // where[rr]-1就是rr所在块左边那个块最右端的元素
27 // 一直到rr暴力增加
28 a[i]+=v,sum[where[rr]]+=v;
29 }
30 for(LL i=where[ll]+1;i<=where[rr]-1;i++)
31 //这里where[ll]和where[rr]均已暴力处理过,所以只枚举中间的块就可以
32 add[i]+=v;
33 }
34 void interval_ask(LL ll,LL rr)
35 {
36 LL ans=0;
37 for(LL i=ll;i<=min(where[ll]*m,rr);i++)
38 ans+=a[i]+add[where[i]];
39 // 暴力求和 ,注意where里面要写ll,因为我们始终是在ll到它的所在区间结尾的元素内循环
40
41 if(where[ll]!=where[rr])
42 for(LL i=(where[rr]-1)*m+1;i<=rr;i++)
43 //注意这里需要加一,因为所有的for都是<=,如果不写+1会加两边
44 ans+=a[i]+add[where[i]];
45
46 for(LL i=where[ll]+1;i<=where[rr]-1;i++)
47 ans+=sum[i]+add[i]*m;
48
49 printf("%lld\n",ans);
50 }
51 int main()
52 {
53 scanf("%lld",&n);
54 scanf("%lld",&q);
55 m=sqrt(n);
56 for(LL i=1;i<=n;i++)
57 scanf("%lld",&a[i]);
58 for(LL i=1;i<=n;i++)
59 where[i]=(i-1)/m+1,sum[where[i]]+=a[i];// 这里的i可以-1(hzwer写的是-1)也可以不写,不写的话第一块的元素个数会是m-1
60
61 for(LL i=1;i<=q;i++)
62 {
63 scanf("%lld",&how);
64 if(how==1)// 区间加
65 {
66 scanf("%lld%lld%lld",&l,&r,&v);
67 interval_add(l,r,v);
68 }
69 else// 单点查询
70 {
71 scanf("%lld%lld",&l,&r);
72 interval_ask(l,r);
73 // where保存的是这个点所属的块,add表示这个块已经增加的元素
74 //a[v]是这个点开始的值,一加就是答案
75 }
76 }
77 return 0;
78 }