首先考虑一个全局的做法。
对于这个 \(1\) 号操作，我们有两种方式做：
如果当前全局最大值是 \(lim\) ，那么第一种方式相当于用 \(x\) 次修改将 \(lim\) 减去 \(x\) ，第二种方式相当于用 \(lim-x\) 次修改将 \(lim\) 减去 \(x\) 。
因为值域只有 \(S=10^5\) 级别，考虑一个修改次数也是 \(O(S)\) 级别的做法。
容易发现两种方式各有优劣：第一种方式如果一直无脑加的话，容易发现，当 \(x>\frac{lim}{2}\) 的时候，就不容易确定上界的位置了，可以用一种很轻松的方法将其卡掉：首先只有 \([1,10^5]\) ，然后第一次操作 \(x=10^5\) ，容易发现操作完了后 \(lim=10^5\) ，接下来由于没有 \(lim\) 的控制，一些 \(x>1\) 的操作都会直接枚举到 \(x\) （这显然是浪费次数的）。
但是如果 \(x\leq \frac{lim}{2}\) ，就可以放心减，因为这个时候 \(lim\) 减去 \(x\) 后还是最大值。
那么对于 \(x>\frac{lim}{2}\) 的部分怎么做呢？这个时候可以考虑用第二种方法，然后将 \(lim\) 定为 \(x\) 。这个时候简单计算一下可以发现没有多余操作了。
接下来就是维护颜色块，考虑用并查集维护，这样十分方便合并。
拓展到区间的做法，将序列分块，每个块用一个并查集然后照做就是了。但是这样空间开不下，所以要离线，然后一个一个块的处理贡献。
代码细节较多，长度较短，本题不卡常，注意实现即可。
因为常数原因，稍微调了一下块大小；并查集合并可以用启发式合并，不过重构比较频繁所以可能作用不大；注意预处理的时候没必要求出每个块的 \(l,r\) ，而是用的时候再求，否则调用这么多次 L[t],R[t] 其实是十分慢的（修正前 \(65\ pts\)，修正后 \(100\ pts\)）。
const int N=1e6+5;
const int M=5e5+5;
const int SqrtN=3e3+5;
int n,m,a[N],ans[N];
struct Query {int op,l,r,x,id;} q[N];
// {{{ Block
int rt[N],fa[N],siz[N],col[N];
inline int find(int x) {return x==fa[x]?x:fa[x]=find(fa[x]);}
/*--------------------------------------------------*/
int sqrtn,tag,lim,id[N],L,R;
inline void init() {
sqrtn=sqrt(n*7/10+1);
lep(i,1,n) id[i]=(i-1)/sqrtn+1;
}
inline void merge(int a,int b) {
if(!rt[b]) rt[b]=rt[a];
else {
if(siz[rt[a]]>siz[rt[b]]) swap(rt[a],rt[b]);
fa[rt[a]]=rt[b],siz[rt[b]]+=siz[rt[a]],col[rt[a]]=siz[rt[a]]=0;
}
col[rt[b]]=b,rt[a]=0;
}
inline void modify(const int &t,int x) {
if(x>lim) return ;
if(x<=lim/2) {rep(i,x,0) merge(i+tag,i+x+tag); tag+=x,lim-=x;}
else {lep(i,x+1,lim) merge(i+tag,i+tag-x); lim=x;}
}
// {{{ solve
inline void get_dsu(const int &t) {
lep(i,L,R) {
if(!rt[a[i]]) col[rt[a[i]]=i]=a[i],siz[i]=0;
++siz[fa[i]=rt[a[i]]],chkmax(lim,a[i]);
}
}
inline void rebuild(const int &t,int l,int r,int x) {
lep(i,L,R) rt[a[i]=col[find(i)]]=siz[i]=0,a[i]-=tag;
lep(i,max(l,L),min(r,R)) if(a[i]>x) a[i]-=x;
get_dsu(t),tag=0;
}
inline void solve(const int &t) {
CLEAR(rt),lim=tag=0;
lep(i,L,R) siz[i]=col[i]=0; get_dsu(t);
lep(_,1,m) {
if(q[_].r<L||q[_].l>R) continue;
if(q[_].op==1) {
if(q[_].l<=L&&R<=q[_].r) modify(t,q[_].x);
else rebuild(t,q[_].l,q[_].r,q[_].x);
} else {
if(!rt[q[_].x+tag]) continue;
if(q[_].l<=L&&R<=q[_].r) ans[q[_].id]+=siz[rt[q[_].x+tag]];
else {
const int _l=max(L,q[_].l),_r=min(R,q[_].r);
lep(i,_l,_r) ans[q[_].id]+=(col[find(i)]==q[_].x+tag);
}
}
}
}
// }}}
// }}}
int query_cnt;
int main() {
IN(n,m);
lep(i,1,n) IN(a[i]);
init();
lep(i,1,m) {
IN(q[i].op,q[i].l,q[i].r,q[i].x);
if(q[i].op==2) q[i].id=++query_cnt;
}
lep(i,1,id[n]) L=(i-1)*sqrtn+1,R=min(L+sqrtn-1,n),solve(i);
lep(i,1,query_cnt) printf("%d\n",ans[i]);
return 0;
}
原文：https://www.cnblogs.com/losermoonlights/p/14196839.html