【Ynoi2018】五彩斑斓的世界
分块。
题目大意：
给定一个数列 $a_1,a_2,a_3,\ldots,a_n$，需要支持两个操作：
- 给定 $l,r,x$，令 $a_l,a_{l+1},a_{l+2},\ldots,a_r$ 中，所有大于 $x$ 的数减去 $x$。
- 给定 $l,r,x$，询问 $a_l,a_{l+1},a_{l+2},\ldots,a_r$ 中 $x$ 的出现次数。
题解：
第二分块。
我们观察一下这个查询操作。把所有大于 $x$ 的数减去 $x$，相当于把所有小于等于 $x$ 的数加上 $x$，然后全局减 $x$。
我们令 $k$ 表示一个数列中的可能最大值。
若 $2x\geq k$，则我们令大于 $x$ 的数减去 $x$ 之后，就没有比 $x$ 大的数了，则 $k$ 在操作后至少减少 $k-x$。
若 $2x\lt k$，则我们令小于等于 $x$ 的数加上 $x$，就没有比 $x$ 小的数了，然后。打全局减的标记，则 $k$ 在操作后至少减少 $x$。
我们发现不管怎么操作，这个 $k$ 都是单调不增的，而 $k$ 初始最大为 $5\times 10^5$。
所以我们如果是对全局进行修改，按照上面的分析，只需要枚举需要修改的那些数值即可。这里枚举的数值的总和为 $O(n)$（默认 $n,m$ 和值域同阶，下同）。
我们希望对每个不同的值的修改能做到 $O(1)$。
考虑使用并查集把相同的值并起来。那么修改的时候，只需要把修改前值对应的并查集的根，连到修改后的值的并查集的根上即可。同时我们需要记录每个数的出现次数，修改的时候直接加过去就好了。
这里有一些很好的性质：我们每次用来连接的都是并查集的根，而一个根连到另一个根之后，这个值本身就消失了。而且我们在这里并不用这个并查集查询。因此这里的并查集并不会进行路径压缩，是 $O(1)$ 的。
然后如果是查询全局某个数的出现位置，那么直接 $O(1)$ 查询即可。
我们考虑查询所有位置的实际值。这里就需要用到并查集的找父亲的操作了。由于这里访问了并查集的所有位置，并进行了路径压缩，所以总复杂度是 $O(n)$ 的。
到这里，接下来的步骤就非常明显了。我们对序列进行分块。
对于一个块的全局修改、全局查询，我们直接按照上述方式去做即可，总时间复杂度 $O(n\sqrt n)$。
对于一个块的部分修改，我们先暴力把每个位置的实际值还原，然后对块进行重构即可。单次 $O(\sqrt n)$。
对于一个块的部分查询，我们直接使用并查集找到每个位置的实际值，然后判断是否相等即可。单次不超过 $O(\sqrt n)$。
总时间复杂度 $O(n\sqrt n)$。
我们来分析空间复杂度。我们需要对每个块记录每个数的出现次数，那么至少需要一个 $O(n\sqrt n)$ 的数组。这非常不可接受。
不过我们可以发现，我们在分块的时候，块是独立的，块与块之间不会相互影响。所以我们可以将操作离线，对每个块都按顺序处理一遍所有的操作，然后把询问的答案累加即可。
这样我们只需要开一个块需要使用的空间，然后共用这些空间即可。
所以空间复杂度 $O(n)$。
Code：
#include<cstdio>
#include<cctype>
#include<cstring>
const int N=1e6+5,B=1200;
#define gc pa==pb&&(pb=(pa=buf)+fread(buf,1,5000000,stdin),pa==pb)?EOF:*pa++
static char buf[5000002],*pa(buf),*pb(buf);
char bwf[9000005],*ww=bwf;
int xx[24];
inline void print(int x){
static int*q=xx;
if(!x)*ww++='0';else{
for(;x;x/=10)*q++=(x%10)^'0';
while(q!=xx)*ww++=*--q;
}
*ww++='\n';
}
inline int readint() {
int x=0;char c=gc;
while(c<'0'||c>'9')c=gc;
for(;c>='0'&&c<='9';c=gc)x=x*10+(c&15);
return x;
}
int op[N],_l[N],_r[N],_x[N];
int n,m,ans[N],a[N],tag,fa[N],mx,buc[200005],L,R,val[N],ifa[N];
inline int find(int x){while(x!=fa[x])x=fa[x]=fa[fa[x]];return x;}
void modify(int x){
if(x>=mx-tag)return;
if(x*2>=mx-tag){
for(int i=mx;i>x+tag;--i)if(buc[i]){
if(buc[i-x])fa[find(ifa[i])]=ifa[i-x];else val[ifa[i-x]=ifa[i]]=i-x;
buc[i-x]+=buc[i],buc[i]=ifa[i]=0;
}
mx=x+tag;
}else{
for(int i=tag+1;i<=tag+x;++i)if(buc[i]){
if(buc[i+x])fa[find(ifa[i])]=ifa[i+x];else val[ifa[i+x]=ifa[i]]=i+x;
buc[i+x]+=buc[i],buc[i]=ifa[i]=0;
}
tag+=x;
}
}
void modify(int l,int r,int x){
l=l<L?L:l,r=r>R?R:r;
for(int i=L;i<=R;++i)ifa[val[i]]=buc[val[i]]=0,a[i]=val[find(i)]-tag;
tag=mx=0;
for(int i=l;i<=r;++i)a[i]-=(a[i]>x)*x;
for(int i=L;i<=R;++i)if(!buc[a[i]]++){
if(mx<a[i])mx=a[i];ifa[val[i]=a[i]]=fa[i]=i;
}else fa[i]=ifa[a[i]];
}
inline void query(int x,int&res){res+=buc[x+tag];}
void query(int l,int r,int x,int&res){
l=l<L?L:l,r=r>R?R:r,x+=tag;
for(int i=l;i<=r;++i)res+=val[find(i)]==x;
}
int main(){
n=readint(),m=readint();
memset(ans,-1,sizeof ans);
for(int i=1;i<=n;++i)a[i]=readint();
for(int i=1;i<=m;++i){
op[i]=readint(),_l[i]=readint(),_r[i]=readint(),_x[i]=readint();
if(op[i]==2)ans[i]=0;
}
for(L=1,R=B;L<=n;L+=B,R+=B){
if(R>n)R=n;
tag=mx=0;
for(int i=L;i<=R;++i)if(!buc[a[i]]++){
if(mx<a[i])mx=a[i];
fa[i]=i,val[i]=a[i],ifa[a[i]]=i;
}else fa[i]=ifa[a[i]];
for(int t=1;t<=m;++t)
if(op[t]==1){
if(_l[t]<=L&&R<=_r[t])modify(_x[t]);else
if(_r[t]>=L&&_l[t]<=R)modify(_l[t],_r[t],_x[t]);
}else{
if(_l[t]<=L&&R<=_r[t])query(_x[t],ans[t]);else
if(_r[t]>=L&&_l[t]<=R)query(_l[t],_r[t],_x[t],ans[t]);
}
for(int i=L;i<=R;++i)ifa[val[find(i)]]=buc[val[find(i)]]=0;
}
for(int i=1;i<=m;++i)if(ans[i]!=-1)print(ans[i]);
fwrite(bwf,ww-bwf,1,stdout);
return 0;
}