Description
维护一个$n(nleqslant 100000)$个元素序列$a_1,a_2,dots,a_n$，有$m(mleqslant 100000)$次操作，分为如下两种。
1. 给定$l,r,x$，将$a_l,a_{l+1},dots,a_r$中所有大于$x$的元素减去$x$
2. 给定$l,r,x$，询问$a_l,a_{l+1},dots,a_r$中，有多少个元素恰好等于$x$
$1leqslant lleqslant rleqslant n,1leqslant a_i,xleqslant 100000$
Solution
多好的题意，可惜是毒瘤数据结构（珂学家狂喜）
这鬼畜分块还专门有一个名字 突刺贯穿的第二分块（这也太怪了）
将序列分为$sqrt n$块
对于一个整块，设其最大值为 $v$ ，要将所有大于 $x$ 的数减去 $x$，则分两种情况讨论：
对于 $2xgeq v$ ，则将所有 $a_i in[x+1,v]$ 平移到 $[1,v-x]$ 上面。枚举每一个值。
对于 $2x < v$ ，则将所有 $[1,x]$ 平移至 $[x+1,2x]$ 上面，并在块内维护一个 $L$ 来统计每一个位置右移了多少。
零散块暴力重构
对于每个块在值域上维护一个并查集
#include<iostream> #include<cstdio> #include<cmath> using namespace std; int n,m,a[200005],pos[200005],maxx[200005],fa[200005],val[200005],tag[200005]; const int S=317; struct DSU { int siz[200005],rt[200005]; int find(int x) { return (fa[x]==x)?fa[x]:fa[x]=find(fa[x]); } void merge(int p,int x,int y) { if(rt[y]) fa[rt[x]+(p-1)*S]=rt[y]+(p-1)*S; else rt[y]=rt[x],val[rt[y]+(p-1)*S]=y; siz[y]+=siz[x],rt[x]=siz[x]=0; } }d[330]; inline int read() { int f=1,w=0; char ch=0; while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9') w=(w<<1)+(w<<3)+ch-'0',ch=getchar(); return f*w; } void maintain(int p) { maxx[p]=0; for(int i=(p-1)*S+1;i<=p*S;i++) { maxx[p]=max(maxx[p],a[i]); if(!d[p].rt[a[i]]) fa[i]=i,d[p].rt[a[i]]=i-(p-1)*S,val[i]=a[i]; else fa[i]=d[p].rt[a[i]]+(p-1)*S; d[p].siz[a[i]]++; } } void update(int p,int l,int r,int x) { for(int i=(p-1)*S+1;i<=min(n,p*S);i++) a[i]=val[d[p].find(i)],d[p].siz[a[i]]=d[p].rt[a[i]]=0,a[i]-=tag[p]; for(int i=(p-1)*S+1;i<=min(n,p*S);i++) fa[i]=0; tag[p]=0; for(int i=l;i<=r;i++) if(a[i]>x) a[i]-=x; maintain(p); } void updateblock(int p,int x) { if(maxx[p]-tag[p]>=(x<<1)) { for(int i=tag[p]+1;i<=tag[p]+x;i++) if(d[p].rt[i]) d[p].merge(p,i,i+x); tag[p]+=x; } else { for(int i=maxx[p];i>tag[p]+x;i--) if(d[p].rt[i]) d[p].merge(p,i,i-x); maxx[p]=min(maxx[p],x+tag[p]); } } int query(int p,int l,int r,int x) { int ret=0; for(int i=l;i<=r;i++) if(val[d[p].find(i)]-tag[p]==x) ret++; return ret; } int queryblock(int p,int x) { if(x+tag[p]>100000) return 0; return d[p].siz[x+tag[p]]; } int main() { n=read(),m=read(); for(int i=1;i<=n;i++) a[i]=read(),pos[i]=(i-1)/S+1; for(int i=1;i<=pos[n];i++) maintain(i); for(int i=1;i<=m;i++) { int opt=read(),l=read(),r=read(),x=read(),bl=pos[l],br=pos[r]; if(opt==1) { if(bl==br) update(bl,l,r,x); else { update(bl,l,bl*S,x),update(br,(br-1)*S+1,r,x); for(int j=bl+1;j<br;j++) updateblock(j,x); } } else { if(bl==br) printf("%d ",query(bl,l,r,x)); else { int ans=query(bl,l,bl*S,x)+query(br,(br-1)*S+1,r,x); for(int j=bl+1;j<br;j++) ans+=queryblock(j,x); printf("%d ",ans); } } } return 0; }