分块总结：时髦之裤

说白了就是南外分块题做的差不多了，来写一篇总结。

简要题意： 给一序列 a，初始时 $a_i=i$，有如下两个操作：
1.将[l,r]每个数改为x，该点增加贡献$|a_i-x|$.
2.询问[l,r]贡献和

样例：

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

27
46

范围1e5.

---

是的，如果不是刻意往分块上想，估计我怎么也想不到是分块。

注意到 $|a_i-x|$，线段树不好做，带修莫队不太会，发现数据范围1e5，$n\sqrt{n}$ 可以过，大胆考虑分块，假设初始序列 $a_i=0$，发现每次修改只会破坏两个块于是我们可以将颜色相同的块与颜色不同的块分开修改，复杂度不超过 $4\sqrt{n}$。

是的，这就是正解。正确性显然，考虑复杂度证明。
每个修改只会破坏两个块，故q次询问只会破坏2q个块，加上由题意原来就破碎的 $\sqrt{n}$ 个块，均摊复杂度不超过 $5\sqrt{n}$，常数够小，稳过。

从代码注释可以看出我有多急（

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+5;
int n,m,B;
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.
void Turn(int l,int r,int x){int ql=l/B;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;else{bz[ql]=1;for(int i=L[ql];i<=R[ql];i++) a[i]=ta[ql];   //ql->i once again!!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!!!}
}
void update(int l,int r,int x){int ql=l/B,qr=r/B;if(ql==qr){Turn(l,r,x);return ;}Turn(l,(ql+1)*B-1,x);Turn(qr*B,r,x);for(int i=ql+1;i<qr;i++){if(!bz[i]){sum[i]+=abs(ta[i]-x);ta[i]=x;}else{for(int j=i*B;j<(i+1)*B;j++) res[j]+=abs(a[j]-x),totres[i]+=abs(a[j]-x);ta[i]=x;bz[i]=0;}}
}
LL query(int l,int r){int ql=l/B,qr=r/B;LL ans=0;if(ql==qr){for(int i=l;i<=r;i++) ans+=res[i]+sum[ql];return ans;}for(int i=l;i<(ql+1)*B;i++) ans+=res[i]+sum[ql];for(int i=qr*B;i<=r;i++) ans+=res[i]+sum[qr];for(int i=ql+1;i<qr;i++) ans+=sum[i]*(R[i]-L[i]+1)+totres[i];return ans;
}
int main(){freopen("a.in","r",stdin);scanf("%d%d",&n,&m);B=sqrt(n);for(int i=0;i<=n/B;i++) L[i]=max(1,i*B),R[i]=min(n,(i+1)*B-1);
//	for(int i=1;i<=n;i++) printf("%d %d\n",L[i/B],R[i/B]);for(int i=1;i<=n;i++) a[i]=i,bz[i/B]=1;while (m--){int op,l,r;scanf("%d",&op);if(op^2){int x;scanf("%d%d%d",&l,&r,&x);update(l,r,x);}else{scanf("%d%d",&l,&r);// 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]);printf("%lld\n",query(l,r));}}return 0;
}