P9410 题解

· · 题解

题目分析

事实上根号分治是完全没必要的，我这里提供一个仅基于分块的时间 O(n\sqrt n)，空间 O(n) 做法。

首先这种问题肯定想分块，朴素的区间加区间求和可以使用散块暴力加，整块懒标记的方法处理。而其实本题也可以用同样的方法：还是先对点的编号分块，之后注意到每次询问只会问到一个连通块，于是我们不完全实时地维护每个连通块的点权和，而是对每个连通块 i 分成 A_i（表示由散块加上来的值）与 B_i（由整块加上来的值）这两部分维护：

前者可以暴力加。后者我们考虑询问时再具体求，这只需对每个连通块维护 s_{i,j} 表示连通块 i 内点编号在第 j 块的点的个数。那么合并连通块 u,v 时令 A_{v}\leftarrow A_{u}+A_{v} 并重构 s 数组即可做到单次 O(\sqrt n) ；询问时有 ans=A_u+B_u=A_u+\sum s_{u,i}\times tag_i，直接扫一遍也可以做到单次 O(\sqrt n)。

现在的空间是 O(n\sqrt n) 的，不过其实很好处理，因为你注意到只需维护 s_{i,j} 中非零的部分，而显然至多有 O(n) 个 s_{i,j} 是非零的，于是对每个 i 开动态数组即可让空间变成 O(n)。

代码

感觉这种做法的代码就挺简洁好懂，非常不错。以下是核心部分代码。

#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ll long long
#define B 475

int n,m,opt,u,v,w,k[200005],L[705],R[705],bh[200005],sz[200005],ns[705];
ll sum[200005],tg[705];
vector <pair<int,int>> sm[200005];
vector <int> num[200005];

signed main()
{
    cin>>n>>m; for(int i=1;i<=n;i++) k[i]=(i-1)/B+1; 
    for(int i=1;i<=k[n];i++) L[i]=(i-1)*B+1,R[i]=min(i*B,n);
    for(int i=1;i<=n;i++) bh[i]=i,sz[i]=1,sm[i].pb(mp(k[i],1)),num[i].pb(i);
    while(m--)
    {
        cin>>opt;
        if(opt==1)
        {
            cin>>u>>v; u=bh[u],v=bh[v]; if(u==v) continue; if(sz[u]>sz[v]) swap(u,v);
            for(auto i:num[u]) bh[i]=v,num[v].pb(i); num[u].clear(); num[u].shrink_to_fit();
            for(auto i:sm[u]) ns[i.fi]+=i.se; for(auto i:sm[v]) ns[i.fi]+=i.se; 
            sm[u].clear(); sm[v].clear(); sm[u].shrink_to_fit(); sm[v].shrink_to_fit();
            for(int i=1;i<=k[n];i++) if(ns[i]) sm[v].pb(mp(i,ns[i])),ns[i]=0; sum[v]+=sum[u]; sz[v]+=sz[u];
        }
        else if(opt==2)
        {
            cin>>u>>v>>w; int uu=k[u],vv=k[v];
            if(uu==vv) {for(int i=u;i<=v;i++) sum[bh[i]]+=w;}
            else
            {
                for(int i=u;i<=R[uu];i++) sum[bh[i]]+=w; for(int i=L[vv];i<=v;i++) sum[bh[i]]+=w;
                for(int i=uu+1;i<=vv-1;i++) tg[i]+=w;
            }
        }
        else {cin>>u; u=bh[u]; ll ans=sum[u]; for(auto i:sm[u]) ans+=(ll)i.se*tg[i.fi]; cout<<ans<<endl;}
    }
}