分塊之區間查詢與區間修改

給出一個長為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 }