普通分块并查集

· · 题解

Part1 前言

序列分块与并查集结合已经是平凡的做法了。

这道题放在省选里就是签到题。

如果不会一定不是能力不行，因为只要学过就会。

前置知识是第二分块，当然这只是因为我是学完第二分块之后过了很久才做这道题，这道题比第二分块简单很多。

为什么这种题我要写题解？

因为有同学被数据范围误导了，还需要卡空间常数？

这道题 50 倍空间（\dfrac{1G}{18M}\approx56）都给你了还要卡空间常数，就算卡过了我把空间开到 64M 你就没了。

当然不排除这道题的空间限制本身具有误导性。

Part2 两种解法的比较

首先是进行序列分块，每一个块维护颜色。

每一种颜色记录一个 fr_c 表示该颜色在块内的第一次出现，其余的每一次出现都可以将父亲置为他，于是可以用并查集路径压缩快速的找到根。

记录 tg_c 表示某种颜色的整体标记，sz_c 表示颜色为 c 的个数。

对于操作 1，在所有整块中：

考虑一种不同的颜色代表 \sqrt n 块钱，初始赋给每个块不超过 n 块钱，整块减少颜色就取了 \sqrt n 块钱，散块修改可能会增加 1 种颜色，就给他 \sqrt n 块钱，总共最多会给 (n+q)\sqrt n 块钱，即时间复杂度为 O((n+q+C)\sqrt n)。

如果每一个块同时维护这些数组，那么空间复杂度为 (n+C)\sqrt n，支持在线，但显然对于一个不强制在线的题目这么做平白增大空间开销是没必要的。

发现这道题查询具有可加性，所以只要对于每一个块，扫描每一个查询，算出这个块的答案，再加起来即可，时间复杂度 O((n+q+C)\sqrt n)，空间 O(n+q+C)。

注意本题的并查集只会在重构时全体 gf，所以并不存在 \alpha(n)。

Part3 后记

不要寄希望于省选时出这种模板套路题，但真的出了不会是致命的。

代码如下：

int n,m,C,f[N],c[N],fr[N],kk,L,R,sz[N];
struct Q{int op,l,r,x,y;}q[N];
ul a[N],ans[N],sm,tg[N];
int gf(int x){return x==f[x]?x:f[x]=gf(f[x]);}
int main(){
    read(n,m,C),kk=1+sqrt(1+n);
    int i,x,y,l,r,X,Y;
    for(x=1;x<=n;++x)read(a[x]);
    for(x=1;x<=n;++x)read(c[x]);
    for(i=1;i<=m;++i){
        read(q[i].op,q[i].l,q[i].r);
        if(q[i].op<3)read(q[i].x,q[i].y);
    }
    for(L=1;L<=n;L=R+1){
        R=min(L+kk,n),sm=0;
        for(x=1;x<=C;++x)fr[x]=tg[x]=sz[x]=0;
        for(x=L;x<=R;++x){
            f[x]=fr[c[x]]?fr[c[x]]:(fr[c[x]]=x);
            sm+=a[x],++sz[c[x]];
        }
        for(i=1;i<=m;++i){
            if(q[i].l>R||q[i].r<L)continue;
            l=max(q[i].l,L),r=min(q[i].r,R);
            X=q[i].x,Y=q[i].y;
            if(l==L&&r==R){
                if(q[i].op==1){
                    if(!fr[X])continue;
                    if(!fr[Y]){
                        c[fr[X]]=Y;
                        swap(fr[X],fr[Y]);
                        swap(tg[X],tg[Y]);
                        swap(sz[X],sz[Y]);
                        continue;
                    }sz[Y]+=sz[X],sz[X]=0;
                    for(x=L;x<=R;++x)c[x]=c[gf(x)];
                    for(x=L;x<=R;++x)
                        if(c[x]==X)
                            a[x]-=tg[Y]-tg[X],c[x]=Y;
                    f[fr[X]]=fr[Y],tg[X]=fr[X]=0;    
                }else if(q[i].op==2){
                    if(!sz[X])continue;
                    sm+=ul(Y)*sz[X];
                    tg[X]+=Y;
                }else ans[i]+=sm;
            }else{
                if(q[i].op==1){
                    for(x=L;x<=R;++x){
                        c[x]=c[gf(x)];
                        if(c[x]==X||c[x]==Y)
                            a[x]+=tg[c[x]];
                    }for(x=l;x<=r;++x)if(c[x]==X)c[x]=Y;
                    sz[X]=sz[Y]=fr[X]=fr[Y]=tg[X]=tg[Y]=0;
                    for(x=L;x<=R;++x)
                        if(c[x]==X||c[x]==Y){
                            f[x]=fr[c[x]]?fr[c[x]]:(fr[c[x]]=x);
                            ++sz[c[x]];
                        }
                }else if(q[i].op==2){
                    for(x=l;x<=r;++x)
                        if(c[gf(x)]==X)a[x]+=Y,sm+=Y;
                }else{
                    for(x=l;x<=r;++x)
                        ans[i]+=tg[c[gf(x)]]+a[x];
                }
            }
        }
    }
    for(i=1;i<=m;++i)if(q[i].op==3)write(ans[i]);
    return 0;
}