[YNOI2018]五彩斑斓的世界&CF896E（分块+并查集）

由于晚上比赛二连（Atcoder&codeforces），外加复习学考，所以暂时没时间写了。

贴个O(n√n)的分块代码，洛谷和cf上都过了，但垃圾bzoj卡不过去，不改了。

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+;

int n,m,B,a[N],b[N],pos[N],l[N],r[N],fa[N],mx[N],sum[N],c[][N],tag[N];

int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}

void build(int id)

{

    for(int i=l[id];i<=r[id];i++)a[i]=b[find(i)],c[id][a[i]]=;

    for(int i=l[id];i<=r[id];i++)fa[i]=i,sum[i]=;

    for(int i=l[id];i<=r[id];i++)

    if(!c[id][a[i]])c[id][a[i]]=i,b[i]=a[i];

    else sum[c[id][a[i]]]+=sum[i],fa[i]=c[id][a[i]];

    while(!c[id][mx[id]])mx[id]--;

}

void update(int id,int x,int y,int v)

{

    for(int i=l[id];i<=r[id];i++)a[i]=b[find(i)];

    for(int i=l[id];i<=r[id];i++)c[id][a[i]]=;

    for(int i=x;i<=y;i++)if(b[find(i)]-tag[id]>v)a[i]-=v;

    for(int i=l[id];i<=r[id];i++)b[i]=a[i],fa[i]=i;

    build(id);

}

void modify(int x,int y,int v)

{

    if(pos[x]==pos[y]){update(pos[x],x,y,v);return;}

    update(pos[x],x,r[pos[x]],v),update(pos[y],l[pos[y]],y,v);

    for(int i=pos[x]+;i<pos[y];i++)

    if(v<mx[i]-tag[i]&&mx[i]-tag[i]<*v)

    {

        for(int j=tag[i]+v+;j<=mx[i];j++)

        if(c[i][j])

            if(!c[i][j-v])c[i][j-v]=c[i][j],b[c[i][j]]=j-v,c[i][j]=;

            else fa[c[i][j]]=c[i][j-v],sum[c[i][j-v]]+=sum[c[i][j]],c[i][j]=;

        while(!c[i][mx[i]])mx[i]--;

    }

    else if(mx[i]-tag[i]>=*v)

    {

        for(int j=tag[i]+;j<=tag[i]+v;j++)

        if(c[i][j])

            if(!c[i][j+v])c[i][j+v]=c[i][j],b[c[i][j]]=j+v,c[i][j]=;

            else fa[c[i][j]]=c[i][j+v],sum[c[i][j+v]]+=sum[c[i][j]],c[i][j]=;

        tag[i]+=v;

    }

}

int query(int x,int y,int v)

{

    int ret=;

    if(pos[x]==pos[y])

    {

        for(int i=x;i<=y;i++)if(b[find(i)]-tag[pos[i]]==v)ret++;

        return ret;

    }

    for(int i=x;i<=r[pos[x]];i++)if(b[find(i)]-tag[pos[i]]==v)ret++;

    for(int i=l[pos[y]];i<=y;i++)if(b[find(i)]-tag[pos[i]]==v)ret++;

    for(int i=pos[x]+;i<pos[y];i++)if(v+tag[i]<N)ret+=sum[c[i][v+tag[i]]];

    return ret;

}

int main()

{

    scanf("%d%d",&n,&m),B=sqrt(n);

    for(int i=;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i],fa[i]=i;

    for(int i=;i<=n;i++)

    {

        r[pos[i]=(i-)/B+]=i;

        if(!l[pos[i]])l[pos[i]]=i;

    }

    for(int i=;i<=pos[n];i++)mx[i]=1e5,build(i);

    while(m--)

    {

        int op,x,y,v;scanf("%d%d%d%d",&op,&x,&y,&v);

        if(op==)modify(x,y,v);else printf("%d\n",query(x,y,v));

    }

}