rt

题面

#include<bits/stdc++.h>
#define fep(i,l,r) for(int i=l;i<=r;i++)
#define defep(i,r,l) for(int i=r;i>=l;i--)
#define fst first
#define scd second
#define lowbit(x) ((x)&(-x))
#define pb(a) push_back(a)
#define sqt(x) (int)(floor(sqrt((long double) x + 1e-16)) )
#define sqr(x) ((x)*(x))
#define Chtholly(x) ios::sync_with_stdio(x)

using namespace std;
const int M=400;
const int N=1e5+123+M;

int blk;

#define Getl(x) ((x-1)*blk+1)
#define Getr(x) (x*blk)

int rt[M][N],cnt[M][N],mx[M],del[M],a[N],bel[N];
int n,m;
int fa[N];

int Findfa(int x){
    if(x==fa[x])return x;
    return fa[x]=Findfa(fa[x]);
}
void Merge(int x,int y,int b){
    //把x合并到y
    //此时x，y是值
    if(rt[b][y]==0){
        rt[b][y]=rt[b][x];rt[b][x]=0;
        cnt[b][y]=cnt[b][x];cnt[b][x]=0;
        a[rt[b][y]]=y;
        return ;
    }
    cnt[b][y]+=cnt[b][x],cnt[b][x]=0;
    x=rt[b][x],y=rt[b][y];
    //合并b块中的x，y的值
    //此时x，y是下标
    if(x==0)return ;
    x=Findfa(x),y=Findfa(y);
    fa[x]=y;//把x集合指向y
}

int b[N];

void Reset(int x){
    for(int i=Getl(x);i<=Getr(x);i++){
        rt[x][a[i]]=cnt[x][a[i]]=0,b[i]=a[Findfa(i)]-del[x];
    }
    for(int i=Getl(x);i<=Getr(x);i++){
        a[i]=b[i];
    }
    del[x]=0;
}

void Update(int x){
    mx[x]=0;
    for(int i=Getl(x);i<=Getr(x);i++)
        if(!rt[x][a[i]])rt[x][a[i]]=i;
    for(int i=Getl(x);i<=Getr(x);i++){
        cnt[x][a[i]]++;
    }
    for(int i=Getl(x);i<=Getr(x);i++)mx[x]=max(mx[x],a[i]);
    for(int i=Getl(x);i<=Getr(x);i++)
        fa[i]=rt[x][a[i]];
}

void Modify(int l,int r,int x){
    int L=bel[l],R=bel[r];
    if(L==R){
        Reset(L);
        for(int i=l;i<=r;i++)
            if(a[i]>x)a[i]-=x;
        Update(L);
    }
    else {
        Reset(L),Reset(R);
        for(int i=l;i<=Getr(L);i++)
            if(a[i]>x)a[i]-=x;
        for(int i=Getl(R);i<=r;i++)
            if(a[i]>x)a[i]-=x;
        Update(L),Update(R);
        for(int i=L+1;i<=R-1;i++){
            if(mx[i]<=x)continue;
            if(mx[i]-del[i]<=x*2){
                for(int j=x+del[i]+1;j<=mx[i];j++)
                    {Merge(j,j-x,i);}
                for(int j=x+del[i];j>=1;j--)
                    if(cnt[i][j]){mx[i]=j;break;}
            }
            if(mx[i]-del[i]>x*2){
                for(int j=del[i]+1;j<=x+del[i];j++)
                    Merge(j,j+x,i);
                del[i]+=x;
            }
        }
    }
}

int Getans(int l,int r,int x){
    int L=bel[l],R=bel[r],ans=0;
    if(L==R){
        Reset(L);
        for(int i=l;i<=r;i++)
            if(a[i]==x)ans++;
        Update(L);
    }
    else{
        Reset(L),Reset(R);
        for(int i=l;i<=Getr(L);i++)
            if(a[i]==x)ans++;
        for(int i=Getl(R);i<=r;i++)
            if(a[i]==x)ans++;
        for(int i=L+1;i<=R-1;i++){
            if(x+del[i]<=1e5)ans+=cnt[i][x+del[i]];
        }
        Update(L);Update(R);
    }
    return ans;
}

signed main(){
    Chtholly(0);
    cin>>n>>m;blk=sqrt(n);
    for(int i=1;i<=n;i++)
        cin>>a[i],bel[i]=(i-1)/blk+1,cnt[bel[i]][a[i]]++;
    for(int i=1;i<=n;i++)mx[bel[i]]=max(mx[bel[i]],a[i]);
    for(int i=1;i<=n;i++)
        if(!rt[bel[i]][a[i]])rt[bel[i]][a[i]]=i;
    for(int i=1;i<=n;i++)fa[i]=rt[bel[i]][a[i]];
    while(m--){
        int kd,l,r,x;
        cin>>kd>>l>>r>>x;
        if(kd==1)
            Modify(l,r,x);
        if(kd==2)
            cout<<Getans(l,r,x)<<endl;
    }
    return 0;
}