题解：P9598 [JOI Open 2018] 山体滑坡

· · 题解

P9598 [JOI Open 2018] 山体滑坡

给一个认为 \alpha(n) 近似于 O(1) 和 n,q,c 同阶时时间复杂度为 O(n\sqrt n) 的做法。

一句话，多次删边和加边，问你 [0,x] 和 [x+1,n-1] 两个点集和其点集间的连边构成的联通块数之和，然后不难发现两部分是独立的，以 [0,x] 为例。

没有修改考虑按 x 排序用并查集加点维护联通块数量，可以做到线性对数；有修改时发现修改对询问的贡献需要花费 \Theta(\text{修改数量}) 的时间，自然想到操作分块，吐槽一下删除操作就是纯纯增加代码量但没有任何思维含量的东西。

我们 B 个操作分一块，块内询问按 x 排序，然后每次询问相当于在原图基础上加 O(B) 条边再问你连通块的数量。

新加边还要撤回操作的话使用可撤销并查集多一个 \log n 的复杂度，此时时间为 O(qB\log n+\frac{nc}{B}\log n)=O(n\sqrt n\log n) ，注意到除了询问的时候加边之外不需要撤销直接路径压缩，可以做到 O(qB\log n+\frac{nc}{B})=O(n\sqrt {n\log n})。

不过都不是很牛，我们想一想怎么优化？

我们考虑在 [0,x] 点集加上 B 条边后的连通块数就是 [0,x] 形成的连通块数减去 B 条边合并的联通块数，考虑把 [0,x] 的联通块按其 fa 缩成一个点，然后再这个 O(B) 个点的新图上看减少了几个连通块，可以用一个新的并查集来维护，然后就能 O(B) 完成单组询问，最后做到 O(qB+\frac{nc}{B})=O(n\sqrt n) 的时间复杂度，当然空间复杂度是 O(n)。

代码：

const int N=1e5+100,B=350;
int n,c,q,x[N],y[N],e[N],op[N],ans[N],fa[N],ff[N],tot,cnt,cnt2,ct;
LL hs[N];
int getf(int x){return x==fa[x]?x:fa[x]=getf(fa[x]);} 
int getf2(int x){return x==ff[x]?x:ff[x]=getf2(ff[x]);}
vector<pii> que[N],opt[N];
vector<int> E[N];
bool vis[N],fl[N];
void merge(int x,int y){
    x=getf(x),y=getf(y);
    if(x==y) return;
    ++cnt,fa[x]=y;
}
void add(int x,int y){
    x=getf(x),y=getf(y);
    if(x==y) return;
    x=getf2(x),y=getf2(y);
    if(x==y) return;
    ff[x]=y,++cnt2;
}
void del(int x,int y){
    x=getf(x),y=getf(y);
    ff[x]=x,ff[y]=y;
}
//bool _ED;
signed main(){
    //fprintf(stderr,"%.20lf MB\n",(&_ST-&_ED)/1048576.0);
    //ios::sync_with_stdio(false);
    //cin.tie(0);cout.tie(0);
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    read(n,c,q);
    rep(i,1,c) {
        read(op[i],x[i],y[i]);
        ++x[i],++y[i];
        if(x[i]>y[i]) swap(x[i],y[i]);
        hs[i]=1ll*x[i]*n+y[i];
    }
    sort(hs+1,hs+1+c);
    ct=unique(hs+1,hs+1+c)-hs-1;
    rep(i,1,c) e[i]=lower_bound(hs+1,hs+1+ct,1ll*x[i]*n+y[i])-hs;
    rep(i,1,q){
        int t,x;
        read(t,x);
        ++t,++x;
        que[t].pb({x,i});
    }
    tot=(c+B-1)/B;
    int l=0,r=0;

    rep(T,1,tot){
        l=r+1,r=min(l+B-1,c);
        rep(i,l,r) fl[e[i]]=1;

        rep(i,1,n) opt[i].clear(),ff[i]=fa[i]=i,E[i].clear();
        rep(i,l,r) for(auto j:que[i]) opt[j.fi].pb({i,j.sc});
        rep(i,1,l-1) if(vis[e[i]]&&(!fl[e[i]])) E[y[i]].pb(x[i]);
        cnt=0;
        rep(u,1,n){
            for(auto v:E[u]) merge(u,v);
            for(auto j:opt[u]){
                int t=j.fi,id=j.sc;
                cnt2=0;
                rep(i,l,t) vis[e[i]]^=1;
                rep(i,l,r) if(vis[e[i]]&&y[i]<=u) add(x[i],y[i]);
                ans[id]-=cnt+cnt2;
                rep(i,l,r) del(x[i],y[i]);
                rep(i,l,t) vis[e[i]]^=1;
            }
        }

        rep(i,1,n) opt[i].clear(),ff[i]=fa[i]=i,E[i].clear();
        rep(i,l,r) for(auto j:que[i]) opt[j.fi+1].pb({i,j.sc});
        rep(i,1,l-1) if(vis[e[i]]&&(!fl[e[i]])) E[x[i]].pb(y[i]);
        cnt=0;
        per(u,n,1){
            for(auto v:E[u]) merge(u,v);
            for(auto j:opt[u]){
                int t=j.fi,id=j.sc;
                cnt2=0;
                rep(i,l,t) vis[e[i]]^=1;
                rep(i,l,r) if(vis[e[i]]&&x[i]>=u) add(x[i],y[i]);
                ans[id]-=cnt+cnt2;
                rep(i,l,r) del(x[i],y[i]);
                rep(i,l,t) vis[e[i]]^=1;
            }
        }
        rep(i,l,r) vis[e[i]]^=1,fl[e[i]]=0;
    }
    rep(i,1,q) write(n+ans[i],'\n');
    //fprintf(stderr,"%.4lf s\n",1.0*clock()/CLOCKS_PER_SEC);
    return 0;
}