分块总结：时髦之裤

说白了就是南外分块题做的差不多了，来写一篇总结。
简要题意： 给一序列 a，初始时                                              a                            i                                  =                         i                              a_i=i                  ai​=i，有如下两个操作：
1.将[l,r]每个数改为x，该点增加贡献                                   ∣                                   a                            i                                  −                         x                         ∣                              |a_i-x|                  ∣ai​−x∣.
2.扣问[l,r]贡献和
样例：

1. 10 4
2. 1 2 7 9
3. 2 1 10
4. 1 3 8 12
5. 2 1 10

复制代码

1. 27
2. 46

复制代码

范围1e5.

---

是的，假如不是刻意往分块上想，估计我怎么也想不到是分块。
留意到                                    ∣                                   a                            i                                  −                         x                         ∣                              |a_i-x|                  ∣ai​−x∣，线段树不好做，带修莫队不太会，发现数据范围1e5，                                   n                                   n                                       n\sqrt n                  nn            ​ 可以过，大胆思量分块，假设初始序列                                              a                            i                                  =                         0                              a_i=0                  ai​=0，发现每次修改只会破坏两个块于是我们可以将颜色雷同的块与颜色不同的块分开修改，复杂度不超过                                    4                                   n                                       4\sqrt n                  4n            ​。
是的，这就是正解。正确性显然，思量复杂度证明。
每个修改只会破坏两个块，故q次扣问只会破坏2q个块，加上由题意原来就破碎的                                              n                                       \sqrt n                  n            ​ 个块，均摊复杂度不超过                                    5                                   n                                       5\sqrt n                  5n            ​，常数够小，稳过。
从代码解释可以看出我有多急（

1. #include<bits/stdc++.h>
2. using namespace std;
3. typedef long long LL;
4. const int N=1e5+5;
5. int n,m,B;
6. LL bz[350],a[N],res[N],totres[N],sum[350],L[350],R[350],ta[350];  //sum:one block,whole res:one block,broken.
7. void Turn(int l,int r,int x){
8.         int ql=l/B;
9.         if(bz[ql]) for(int i=l;i<=r;i++) res[i]+=abs(a[i]-x),totres[ql]+=abs(a[i]-x),a[i]=x;
10.         else{
11.                 bz[ql]=1;
12.                 for(int i=L[ql];i<=R[ql];i++) a[i]=ta[ql];   //ql->i once again!!
13.                 for(int i=l;i<=r;i++) res[i]+=abs(ta[ql]-x),totres[ql]+=abs(ta[ql]-x),a[i]=x;  //ql->i debug 2h!!!
14.         }
15. }
16. void update(int l,int r,int x){
17.         int ql=l/B,qr=r/B;
18.         if(ql==qr){
19.                 Turn(l,r,x);
20.                 return ;
21.         }
22.         Turn(l,(ql+1)*B-1,x);
23.         Turn(qr*B,r,x);
24.         for(int i=ql+1;i<qr;i++){
25.                 if(!bz[i]){
26.                         sum[i]+=abs(ta[i]-x);
27.                         ta[i]=x;
28.                 }else{
29.                         for(int j=i*B;j<(i+1)*B;j++) res[j]+=abs(a[j]-x),totres[i]+=abs(a[j]-x);
30.                         ta[i]=x;
31.                         bz[i]=0;
32.                 }
33.         }
34. }
35. LL query(int l,int r){
36.         int ql=l/B,qr=r/B;
37.         LL ans=0;
38.         if(ql==qr){
39.                 for(int i=l;i<=r;i++) ans+=res[i]+sum[ql];
40.                 return ans;
41.         }
42.         for(int i=l;i<(ql+1)*B;i++) ans+=res[i]+sum[ql];
43.         for(int i=qr*B;i<=r;i++) ans+=res[i]+sum[qr];
44.         for(int i=ql+1;i<qr;i++) ans+=sum[i]*(R[i]-L[i]+1)+totres[i];
45.         return ans;
46. }
47. int main(){
48.         freopen("a.in","r",stdin);
49.         scanf("%d%d",&n,&m);B=sqrt(n);
50.         for(int i=0;i<=n/B;i++) L[i]=max(1,i*B),R[i]=min(n,(i+1)*B-1);
51. //        for(int i=1;i<=n;i++) printf("%d %d\n",L[i/B],R[i/B]);
52.         for(int i=1;i<=n;i++) a[i]=i,bz[i/B]=1;
53.         while (m--){
54.                 int op,l,r;scanf("%d",&op);
55.                 if(op^2){
56.                         int x;scanf("%d%d%d",&l,&r,&x);
57.                         update(l,r,x);
58.                 }else{
59.                         scanf("%d%d",&l,&r);
60.                         // for(int i=l;i<=r;i++) printf("a:%d ta:%d res:%lld sum:%lld\n",a[i],ta[i/B],res[i],sum[i/B]);
61.                         printf("%lld\n",query(l,r));
62.                 }
63.         }
64.         return 0;
65. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。