具体思路

注意本题不保证是一棵树，因此不能直接 LCT 解决连通性问题。

这里采用线段树分治的方式解决。

我们知道 LCT 可以在线解决树的增删边连通性问题，而线段树分治在离线解决树的增删边连通性问题的基础上还可以解决图的增删边连通性问题。

学过线段树优化建图的同学就很好理解以下部分。

我们在时间轴上建一棵线段树，每个节点掌管着一段时间。我们开一个 vector 来存当前节点所掌管的区间内出现了哪些边，设一条边在图中出现的时间为 $[l,r]$，那么我们每次只需要找到第一次和这个区间有交集的节点，并在那个节点的vector内加入这条边，原因等会说。

我们离线操作，将所有操作在线段树上进行。在最后统一询问。

好，那么现在我们考虑如何解决连通性问题。众所周知，并查集可以解决图的连通性问题吗，因此考虑线段树套并查集。

我们来讲分治部分。

我们每访问一个节点，就将它所包含的边加入并查集，然后向左右两边分治。由于我们当前区间包含了下面的子区间，因此边只建一次就可以保证时间复杂度，也就解释了上面的问题。

我们每次访问到线段树的底部，就可以判断当前所在时间的操作是不是询问操作，如果是，就看一下查询的两个节点是不是在同一个并查集内部就好了，如果是，直接输出。

为什么我们可以直接输出？因为我们每次都是先分治左区间，在分治右区间，因此时间一定是从左到右的，也就是按照操作先后顺序来的。

最后就是一个很重要的问题，我们需要支持删边操作，而并查集并不支持删边操作，这时候我们需要可撤销并查集。怎么实现呢？我们需要一个栈，分治前存一下当前的栈顶。分治时将并查集的合并操作插入栈内。分治完后当前栈顶到 $last$ 之间的部分直接弹出栈内就可以支持回溯功能。

由于我们进行了删边操作，因此当前并查集内的点的父亲可能现在和它不连通了，这时候我们就不可以路径压缩了，为了保证复杂度，我们采用按秩合并的优化方式来保证复杂度。

时间复杂度：分治本身复杂度是 $O(n \log n)$ 的，按秩合并优化的并查集单次操作复杂度是 $O(\log n)$ 的，因此总的时间复杂度是 $O(n \log^2 n)$。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m;char op[10];
struct query{
	int x,y,type;
}q[N];
struct node{
	int x,y;
}sta[4*N];
int top;
map<int,int>ma[2*N];
vector<int>t[2*N];
int fa[2*N],siz[2*N];
int get(int x){
	if(fa[x]==x)return x;
	return get(fa[x]);
}
void merge(int tx,int ty){
	if(tx!=ty){
		if(siz[tx]>siz[ty])swap(tx,ty);
		fa[tx]=ty;
		siz[ty]+=siz[tx];
		sta[++top]={tx,ty};
	}
}
struct trnode{
	int l,r,lc,rc;
}tr[4*N];
int trlen;
void build(int nl,int nr){
	trlen++;int now=trlen;
	tr[now]=trnode{nl,nr,-1,-1};
	if(nl==nr)return;
	else{
		int mid=(nl+nr)>>1;
		tr[now].lc=trlen+1;build(nl,mid);
		tr[now].rc=trlen+1;build(mid+1,nr);
	}
}
void change(int now,int nl,int nr,int l,int r,int x){
	if(l<=nl&&nr<=r){
		t[now].push_back(x);
		return;
	}
	int mid=(nl+nr)>>1;
	int lc=tr[now].lc,rc=tr[now].rc;
	if(l<=mid)change(lc,nl,mid,l,r,x);
	if(mid<r)change(rc,mid+1,nr,l,r,x);
}
void solve(int now,int nl,int nr){
	int last=top;
	for(int i:t[now]){
		int tx=get(q[i].x),ty=get(q[i].y);
		if(tx!=ty){
			merge(tx,ty);
		}
	}
	if(nl==nr){
		if(q[nl].type==3){
			int tx=get(q[nl].x),ty=get(q[nl].y);
			if(tx==ty)puts("Y");
			else puts("N");
		}
	}
	else{
		int mid=(nl+nr)>>1;
		int lc=tr[now].lc,rc=tr[now].rc;
		solve(lc,nl,mid);
		solve(rc,mid+1,nr);
	}
	while(top>last){
		siz[sta[top].y]-=siz[sta[top].x];
		fa[sta[top].x]=sta[top].x;
		top--;
	}
	return;
}
int get(int x,int y){
	return (x-1)*n+y;
}
int main(){
	scanf("%d",&n);
	build(1,N-5);
	while(scanf("%s",op+1)!=EOF&&op[1]!='E'){
		m++;
		int r1,c1,r2,c2;
		scanf("%d%d%d%d",&r1,&c1,&r2,&c2);
		int x=get(r1,c1),y=get(r2,c2);
		if(x>y)swap(x,y);
		q[m].x=x,q[m].y=y;
		if(op[1]=='O'){
			ma[x][y]=m;
			q[m].type=1;
		}
		if(op[1]=='C'){
			change(1,1,N-5,ma[x][y],m-1,m);
			ma[x].erase(ma[x].find(y));
			q[m].type=2;
		}
		if(op[1]=='A'){
			q[m].type=3;
		}
	}
	for(int i=1;i<=2*n;i++){
		for(map<int,int>::iterator it=ma[i].begin();it!=ma[i].end();it++){
			change(1,1,N-5,it->second,m,it->second);
		}
	}
	for(int i=1;i<=2*n;i++){
		fa[i]=i;
		siz[i]=1;
	}
	solve(1,1,N-5);
	return 0;
}

#include <algorithm>
#include <map>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T power(T base,T index,T mod){return((index<=1)?(index?base:1):(power(base*base%mod,index>>1,mod)*power(base,index&1,mod)))%mod;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(!b)return y=0,x=1,a;T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}
template<typename T,typename Rand>
class Heap_DSU
{
    private:
        std::vector<T>Fath,Prior,Hty;
        T root(T p){return(p==Fath[p])?p:root(Fath[p]);}
    public:
        voi build(T n,Rand rng=Rand())
        {
            Fath.resize(n),Prior.resize(n),Hty.clear();
            for(T i=0;i<n;i++)Fath[i]=i,Prior[i]=rng();
        }
        bol connected(uint u,uint v){return root(u)==root(v);}
        bol merge(T u,T v)
        {
            if((u=root(u))==(v=root(v)))return Hty.push_back(u),false;
            if(Prior[u]<Prior[v])std::swap(u,v);
            return Fath[u]=v,Hty.push_back(u),true;
        }
        bol revoke()
        {
            if(Hty.empty())return false;
            T p=Hty.back();Hty.pop_back();
            if(Fath[p]==p)return false;
            return Fath[p]=p,true;
        }
};
typedef std::pair<uint,uint>Pair;
struct Seg
{
    std::vector<Pair>Way;uint len;Seg*L,*R;
    voi build(uint n){if((len=n)>1)L=new Seg,R=new Seg,L->build(len>>1),R->build(len-(len>>1));}
    voi insert(uint l,uint r,Pair p)
    {
        if(!l&&r==len){Way.push_back(p);return;}
        if(l<(len>>1))
            if(r<=(len>>1))L->insert(l,r,p);
            else L->insert(l,len>>1,p),R->insert(0,r-(len>>1),p);
        else R->insert(l-(len>>1),r-(len>>1),p);
    }
};
ullt Ra=1;const ullt Rb=10007,Rc=114513;struct rng{uint operator()(){return Ra=Ra*Rb+Rc;}};
Heap_DSU<uint,rng>U;
chr C[10];Pair P[114514];uint Op[114514];
bol Ans[114514];uint t=0;
uint hash(uint a,bol b){return a<<1|b;}
std::map<Pair,uint>M;Seg S;
voi dfs(Seg*S,uint cnt)
{
    uint k=0;for(auto w:S->Way)U.merge(w.first,w.second),k++;
    if(S->len==1)
    {
        if(!Op[cnt])Ans[t++]=U.connected(P[cnt].first,P[cnt].second);
    }
    else dfs(S->L,cnt),dfs(S->R,cnt+S->L->len);
    while(k--)U.revoke();
}
int main()
{
    uint n,m=0,r,c;scanf("%u%u",&n),U.build(n<<1);
    while(scanf("%s",C)==1&&*C!='E')
    {
        Op[m]=*C=='A'?0:(*C=='O'?1:2);
        scanf("%u%u",&r,&c),P[m].first=hash(c-1,r-1);
        scanf("%u%u",&r,&c),P[m].second=hash(c-1,r-1);
        if(P[m].first>P[m].second)std::swap(P[m].first,P[m].second);
        m++;
    }
    S.build(m);
    for(uint i=0;i<m;i++)if(Op[i]==1)M[P[i]]=i;else if(Op[i]==2)S.insert(M[P[i]],i,P[i]),M.erase(P[i]);
    for(auto w:M)S.insert(w.second,m,w.first);
    dfs(&S,0);
    for(uint i=0;i<t;i++)puts(Ans[i]?"Y":"N");
    return 0;
}

同见于我的洛谷博客

前言

可能大多数人看到这题就一眼动态图连通性秒了。

但是我发现自己不会敲动态图连通性……

于是，提供一种离线做法。

什么，LCT？

LCT 多难打，放一个更加暴力而简约的离线做法。

思路

线段树分治。

考虑到每条道路都有一个寿命，即从某时刻到某时刻里存在，我们具备了线段树分治的一个先决条件。特别的，如果最后都没有死，我们最后杀掉它。

我们维护一个时光序列，即某时刻中有的道路，那么对每条道路，我们在时光序列的某段中同时插入，最后对时光序列每个询问点进行查询即可，使用并查集复杂度是 $O(nm\alpha(n))$ 的。

这不就暴力吗。

考虑到时光序列可以形如一颗 Leafy Tree（把实际信息存在叶子节点的树）的，我们用线段树维护它，插入边时就是在线段树上区间插入，查询时 dfs 一遍线段树即可。

什么，你问我 dfs 时怎么统计贡献？

使用带撤销并查集即可。

什么，你不会带撤销并查集？

其实就是不用路径压缩而用其它优化（如按秩合并）的并查集，开栈记录下 merge 过程，撤销操作就取栈顶回退即可。

复杂度 $O(n+m\log m\log n)$。

Code

带撤销并查集使用按秩合并没有精神，以下代码利用 Treap 的思想，封装了一个 Heap_DSU。

#include <algorithm>
#include <map>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T power(T base,T index,T mod){return((index<=1)?(index?base:1):(power(base*base%mod,index>>1,mod)*power(base,index&1,mod)))%mod;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(!b)return y=0,x=1,a;T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}
template<typename T,typename Rand>
class Heap_DSU
{
    private:
        std::vector<T>Fath,Prior,Hty;
        T root(T p){return(p==Fath[p])?p:root(Fath[p]);}
    public:
        voi build(T n,Rand rng=Rand())
        {
            Fath.resize(n),Prior.resize(n),Hty.clear();
            for(T i=0;i<n;i++)Fath[i]=i,Prior[i]=rng();
        }
        bol connected(uint u,uint v){return root(u)==root(v);}
        bol merge(T u,T v)
        {
            if((u=root(u))==(v=root(v)))return Hty.push_back(u),false;
            if(Prior[u]<Prior[v])std::swap(u,v);
            return Fath[u]=v,Hty.push_back(u),true;
        }
        bol revoke()
        {
            if(Hty.empty())return false;
            T p=Hty.back();Hty.pop_back();
            if(Fath[p]==p)return false;
            return Fath[p]=p,true;
        }
};
typedef std::pair<uint,uint>Pair;
struct Seg
{
    std::vector<Pair>Way;uint len;Seg*L,*R;
    voi build(uint n){if((len=n)>1)L=new Seg,R=new Seg,L->build(len>>1),R->build(len-(len>>1));}
    voi insert(uint l,uint r,Pair p)
    {
        if(!l&&r==len){Way.push_back(p);return;}
        if(l<(len>>1))
            if(r<=(len>>1))L->insert(l,r,p);
            else L->insert(l,len>>1,p),R->insert(0,r-(len>>1),p);
        else R->insert(l-(len>>1),r-(len>>1),p);
    }
};
ullt Ra=1;const ullt Rb=10007,Rc=114513;struct rng{uint operator()(){return Ra=Ra*Rb+Rc;}};
Heap_DSU<uint,rng>U;
chr C[10];Pair P[114514];uint Op[114514];
bol Ans[114514];uint t=0;
uint hash(uint a,bol b){return a<<1|b;}
std::map<Pair,uint>M;Seg S;
voi dfs(Seg*S,uint cnt)
{
    uint k=0;for(auto w:S->Way)U.merge(w.first,w.second),k++;
    if(S->len==1)
    {
        if(!Op[cnt])Ans[t++]=U.connected(P[cnt].first,P[cnt].second);
    }
    else dfs(S->L,cnt),dfs(S->R,cnt+S->L->len);
    while(k--)U.revoke();
}
int main()
{
    uint n,m=0,r,c;scanf("%u%u",&n),U.build(n<<1);
    while(scanf("%s",C)==1&&*C!='E')
    {
        Op[m]=*C=='A'?0:(*C=='O'?1:2);
        scanf("%u%u",&r,&c),P[m].first=hash(c-1,r-1);
        scanf("%u%u",&r,&c),P[m].second=hash(c-1,r-1);
        if(P[m].first>P[m].second)std::swap(P[m].first,P[m].second);
        m++;
    }
    S.build(m);
    for(uint i=0;i<m;i++)if(Op[i]==1)M[P[i]]=i;else if(Op[i]==2)S.insert(M[P[i]],i,P[i]),M.erase(P[i]);
    for(auto w:M)S.insert(w.second,m,w.first);
    dfs(&S,0);
    for(uint i=0;i<t;i++)puts(Ans[i]?"Y":"N");
    return 0;
}

一些经验 / 非经验

可以离线（经验）：

• SP9576
• SP9577
• loj121
• P2147
• P3767

强制在线（非经验）：

• loj122
• P5247