在校网上做题时发现原题QwQ……
题解：
这很明显是求动态图的连通性啊，果断线段树分治。
线段树分治就是按时间进行分治，利用按秩合并的并查集合并/分离操作维护连通性，LOJ似乎有一道非常好的模板题：「离线可过」动态图连通性。
剩下的就是粘板子了，存储边时用map维护即可。
时间复杂度 (O(m log m))(m为操作数)。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m=0;
struct T { int l,r;vector <int> id; };T t[400010];
struct P { int opt,x,y; };P q[100010];
struct S { int x,dep; };S sta[400010];
map <int,int> ma[200010];
char s[10];
int fa[200010],dep[200010],top=0;
inline int Max(int x,int y) { return x>y? x:y; }
void build(int u,int l,int r) {
t[u].l=l,t[u].r=r; if(l>=r) return ;
int mid=(l+r)>>1; build(u*2,l,mid),build(u*2+1,mid+1,r);
}
void ins(int u,int l,int r,int w) {
if(l==t[u].l&&r==t[u].r) { t[u].id.push_back(w);return ; }
int mid=(t[u].l+t[u].r)>>1;
if(r<=mid) ins(u*2,l,r,w); else if(l>mid) ins(u*2+1,l,r,w);
else ins(u*2,l,mid,w),ins(u*2+1,mid+1,r,w);
}
inline int find(int x) { return x==fa[x]? x:find(fa[x]); }
void Union(int x,int y) {
x=find(x),y=find(y); if(x==y) return ;
if(dep[x]<dep[y]) x^=y,y^=x,x^=y;
fa[y]=x;sta[++top]=(S){y,dep[y]},sta[++top]=(S){x,dep[x]};
dep[x]=Max(dep[x],dep[y]+1);
}
void dfs(int u) {
int Now=top;
for(int i=0;i<t[u].id.size();i++) Union(q[t[u].id[i]].x,q[t[u].id[i]].y);
if(t[u].l>=t[u].r) {
if(q[t[u].l].opt==3)
find(q[t[u].l].x)==find(q[t[u].l].y)? puts("Y"):puts("N");
return ;
}
dfs(u*2),dfs(u*2+1);
while(top>Now) fa[sta[top].x]=sta[top].x,dep[sta[top].x]=sta[top].dep,--top;
}
int main() {
scanf("%d",&n),build(1,1,100000);
for(int i=1;i<=n+n;i++) fa[i]=i,dep[i]=1;
for(int i=1;;++i) {
scanf("%s",s); if(s[0]=='E') break;
int a,b,c,d,x,y; ++m;
scanf("%d%d%d%d",&a,&b,&c,&d),x=(a-1)*n+b,y=(c-1)*n+d;
if(x>y) x^=y,y^=x,x^=y;
q[m].x=x,q[m].y=y;
if(s[0]=='O') q[m].opt=1,ma[x][y]=i;
else if(s[0]=='C')
ins(1,ma[x][y],i-1,i),ma[x].erase(ma[x].find(y)),q[m].opt=2;
else q[m].opt=3;
}
for(int i=1;i<=n+n;i++)
for(map<int,int>::iterator it=ma[i].begin();it!=ma[i].end();++it)
ins(1,it->second,m,it->second);
dfs(1);
return 0;
}