【SHOI2008】堵塞的交通 | Mrsrz's blog

线段树分治+可撤销并查集

题目大意：

给定一个 $2\times C$ 的网格图，初始没有边。需要支持加边（保证在网格上）、删边、询问两点间连通性。

题解：

这题没有强制在线，所以可以直接离线线段树分治解决。

用线段树分治判断动态图连通性的基本套路。

对时间开线段树，然后离线得到每条边的出现时间，并将其加入线段树上。然后把询问插到线段树对应叶结点中。

处理完后，遍历整棵线段树，到达一个结点时把这些边加上，用并查集来维护。

退出一个结点时，需要撤销相应的加边操作，用栈维护即可。为了保证并查集复杂度的正确性，这里要按秩合并，不能路径压缩，则单次复杂度为非均摊的 $O(\log n)$。

到达叶结点时，直接把询问在并查集上查询即可。

时间复杂度 $O(T\log C\log T)$。

Code：

#include<iostream>
#include<algorithm>
#include<vector>
#define get(x,y)((x-1)*n+y)
using namespace std;
const int N=2e5+5;
int n;
vector<pair<int,int>>vec[N<<2];
pair<int,int>que[N];
int down[N],Right[N],sz[N],fa[N],top;
char s[10],ans[N];
inline int find(int x){while(x!=fa[x])x=fa[x];return x;}
int sta[N*2];
void insert(int l,int r,int o,const int&L,const int&R,const pair<int,int>&v){
    if(L<=l&&r<=R)vec[o].push_back(v);else{
        const int mid=l+r>>1;
        if(L<=mid)insert(l,mid,o<<1,L,R,v);
        if(mid<R)insert(mid+1,r,o<<1|1,L,R,v);
    }
}
void solve(int l,int r,int o){
    const int TOP=top;
    for(auto it:vec[o]){
        int x=find(it.first),y=find(it.second);
        if(x!=y){
            if(sz[x]<sz[y])swap(x,y);
            sta[++top]=y;
            sz[x]+=sz[y],fa[y]=x;
        }
    }
    if(l==r){
        if(que[l].first)
        ans[l]=(find(que[l].first)==find(que[l].second))?'Y':'N';
    }else{
        const int mid=l+r>>1;
        solve(l,mid,o<<1),solve(mid+1,r,o<<1|1);
    }
    while(top!=TOP){
        int y=sta[top--];
        sz[fa[y]]-=sz[y],fa[y]=y;
    }
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    int T=0;
    while(cin>>s&&*s!='E'){
        ++T;
        int r1,c1,r2,c2;
        cin>>r1>>c1>>r2>>c2;
        if(r1>r2)swap(r1,r2),swap(c1,c2);else
        if(r1==r2&&c1>c2)swap(c1,c2);
        const int id1=get(r1,c1),id2=get(r2,c2);
        switch(*s){
            case'O':{
                if(r1==r2&&!Right[id1])Right[id1]=T;
                if(r1<r2&&!down[id1])down[id1]=T;
                break;
            }
            case'C':{
                if(r1==r2)insert(1,131072,1,Right[id1],T,make_pair(id1,id2)),Right[id1]=0;
                if(r1<r2)insert(1,131072,1,down[id1],T,make_pair(id1,id2)),down[id1]=0;
                break;
            }
            case'A':{
                que[T]=make_pair(id1,id2);
                break;
            }
        }
    }
    for(int i=1;i<=2*n;++i){
        if(Right[i])
        insert(1,131072,1,Right[i],T,make_pair(i,i+1));
        if(down[i])
        insert(1,131072,1,down[i],T,make_pair(i,i+n));
    }
    for(int i=1;i<=2*n;++i)fa[i]=i,sz[i]=1;
    solve(1,131072,1);
    for(int i=1;i<=T;++i)
    if(ans[i])cout.put(ans[i]),cout.put('\n');
    return 0;
}