【题解】「Ynoi2018」五彩斑斓的世界 分块+并查集 — Qiuly

首先考虑一个全局的做法。

对于这个 $1$ 号操作，我们有两种方式做：

• 将所有 $\leq x$ 的数加上 $x$，然后全局打上一个减法标记。
• 将所有 $>x$ 的数减去 $x$ 。

如果当前全局最大值是 $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$ 。这个时候简单计算一下可以发现没有多余操作了。

接下来就是维护颜色块，考虑用并查集维护，这样十分方便合并。

拓展到区间的做法，将序列分块，每个块用一个并查集然后照做就是了。但是这样空间开不下，所以要离线，然后一个一个块的处理贡献。

• 整块修改：按照上面的做法即可，修改权值相当于合并并查集。
• 散块修改：重构并查集，重构的复杂度是 $O(\sqrt{n})$ 的，是正确的。
• 整块查询：直接查询对应并查集的大小即可。
• 散块查询：暴力枚举这些位置，然后找到它们归属的并查集的数是否等于 $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;
}