给定长度 (n) 的序列 (a)，(m) 个操作：
- 对于区间 ([l,r]) 中的大于 (x) 的数减去 (x)
- 查询区间 ([l,r]) 中等于 (x) 的数的个数
(a_ile 10^5,n,mle 10^5)
看到值域相当小，于是可以在这上面入手
考虑对序列分块，则每块的最大值的和不超过 (O(nsqrt{n}))
那么对于整块的情况，设这一块的最大值为 (max)，要对其中大于 (x) 的数减去 (x)，则：
- 如果 (2x<max)，则将所有的 ([1,x]) 中的数移动到 ([x+1,2x]) 中，并对于每个块维护一个 (tag) 表示他向右移动了多少。设 ([1,x]) 中的数有 (k) 个，则花费 (O(kx)) 的复杂度把这个块的 (max) 降低了 (x)
- 如果 (2xge max)，则将所有的 ([x+1,max]) 的数移动到 ([1,max-x]) 中。设 ([x+1,max]) 中的数有 (k) 个，则花费 (O(k(max-x))) 的复杂度把这个块的 (max) 降低了 (max-x)
对于散块直接重构
于是可以对每个块的每个值分别搞一个并查集，并记录一下大小
然后因为所有块的最大值之和有保证，所以复杂度就对了
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#define reg register
#define EN puts("")
inline int read(){
reg int x=0;reg int y=1;reg char c=getchar();
while(c<'0'||c>'9'){if(c=='-')y=0;c=getchar();}
while(c>='0'&&c<='9') x=x*10+(c^48),c=getchar();
return y?x:-x;
}
#define N 100522
#define B 322
int blocksize,blocknum;
int n,a[N];
int belong[N],left[B],right[B];
struct Node{int root,num;};
Node v[B][N];
int pos[N],fa[N];
int max[N],tag[N];
inline int find(reg int k){return k==fa[k]?k:fa[k]=find(fa[k]);}
inline void build(reg int o){
max[o]=0;
for(reg int i=left[o];i<=right[o];i++){
max[o]=std::max(max[o],a[i]);
if(v[o][a[i]].root) fa[i]=v[o][a[i]].root;
else v[o][a[i]].root=i,fa[i]=i,pos[i]=a[i];
v[o][a[i]].num++;
}
}
inline void merge(reg int o,int s,int t){
Node *S=&v[o][s],*T=&v[o][t];
if(T->root) fa[S->root]=T->root;
else T->root=S->root,pos[T->root]=t;
T->num+=S->num;
S->num=S->root=0;
}
inline void pushdown(reg int o){
for(reg int i=left[o];i<=right[o];i++){
a[i]=pos[find(i)];
v[o][a[i]].root=v[o][a[i]].num=0;
a[i]-=tag[o];
}
for(reg int i=left[o];i<=right[o];i++) fa[i]=0;
tag[o]=0;
}
inline void maketag(reg int o,reg int x){
if((x<<1)<max[o]-tag[o]){
for(reg int i=tag[o]+1;i<=tag[o]+x;i++)if(v[o][i].root) merge(o,i,i+x);
tag[o]+=x;
}
else{
for(reg int i=max[o];i>tag[o]+x;i--)if(v[o][i].root) merge(o,i,i-x);
max[o]=std::min(max[o],tag[o]+x);
}
}
int main(){
n=read();int m=read();
blocksize=std::sqrt(n);blocknum=(n-1)/blocksize+1;
std::memset(left,0x3f,sizeof left);
for(reg int i=1;i<=n;i++){
a[i]=read();belong[i]=(i-1)/blocksize+1;
left[belong[i]]=std::min(left[belong[i]],i);right[belong[i]]=std::max(right[belong[i]],i);
}
for(reg int i=1;i<=blocknum;i++) build(i);
int op;reg int l,r,x;while(m--){
op=read();l=read();r=read();x=read();
int L=belong[l],R=belong[r];
if(op==1){
if(L^R){
pushdown(L);pushdown(R);
for(reg int i=l;i<=right[L];i++)if(a[i]>x) a[i]-=x;
for(reg int i=left[R];i<=r;i++)if(a[i]>x) a[i]-=x;
build(L);build(R);
for(reg int i=L+1;i<R;i++) maketag(i,x);
}
else{
pushdown(L);
for(reg int i=l;i<=r;i++)if(a[i]>x) a[i]-=x;
build(L);
}
}
else{
int ans=0;
if(L^R){
for(reg int i=l;i<=right[L];i++) ans+=(pos[find(i)]-tag[L]==x);
for(reg int i=left[R];i<=r;i++) ans+=(pos[find(i)]-tag[R]==x);
for(reg int i=L+1;i<R;i++) ans+=(tag[i]+x>=N?0:v[i][tag[i]+x].num);
}
else for(reg int i=l;i<=r;i++) ans+=(pos[find(i)]-tag[L]==x);
printf("%d
",ans);
}
}
return 0;
}