这题说白了就是一个支持加边和删边的图连通性维护，不过鉴于图的特殊性，可以直接线段树(听说标算就是这个……)。
然而我人比较懒，不想思考怎么线段树，于是乎写了一发分治并查集，1A我真是感动……
话说一时没想起来怎么写能撤销的按秩合并，于是乎写了个随机合并(反正期望复杂度都是logn的)，代码开头那个玩意儿就是手写的随机数生成器……(我会说模数取998244353之后即使int有溢出也能保证循环节在一千万以上嘛……)
第一发分治并查集，又学会了一个新技能哈哈……
话说这份代码在bzoj上被卡了，真是忧伤……
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
const int maxn=;
inline int randint(){
static int a=,b=,c=,x=,p=;
x=a*x*x+b*x+c;x%=p;
return x<?(x=-x):x;
}
struct A{int u,v,tp;}a[maxn];
void addedge(int,int,int);
void addquery(int,int,int);
void solve(int,int,int);
int findroot(int);
void mergeset(int,int,vector<int>&);
int id[][maxn],cnt=,prt[maxn<<],qu[maxn<<],qv[maxn<<];
int n,m=,x1,y1,x2,y2,x,y,s,t;
vector<int>u[maxn<<],v[maxn<<],stk[maxn<<];
map<pair<int,int>,int>mp;
char c[];
int main(){
freopen("bzoj_1018.in","r",stdin);
freopen("bzoj_1018.out","w",stdout);
scanf("%d",&n);
for(int i=;i<=n;i++){
id[][i]=++cnt;
id[][i]=++cnt;
}
for(int i=;i<=cnt;i++)prt[i]=i;
for(int &i=m;scanf("%s",c)==&&strcmp(c,"Exit");i++){
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
x=id[x1][y1];y=id[x2][y2];
if(x>y)swap(x,y);
a[i].u=x;a[i].v=y;
if(!strcmp(c,"Open"))a[i].tp=;
else if(!strcmp(c,"Close"))a[i].tp=;
else a[i].tp=;
}
for(int i=;i<=m;i++){
x=a[i].u;y=a[i].v;
if(a[i].tp==){
if(!mp.count(make_pair(x,y)))mp[make_pair(x,y)]=i;
}
else if(a[i].tp==){
if(mp.count(make_pair(x,y))){
s=mp[make_pair(x,y)];
t=i;
addedge(,m,);
mp.erase(make_pair(x,y));
}
}
else{
t=i;
addquery(,m,);
}
}
for(map<pair<int,int>,int>::iterator it=mp.begin();it!=mp.end();it++){
x=it->first.first;
y=it->first.second;
s=it->second;
t=m;
addedge(,m,);
}
solve(,m,);
return ;
}
void addedge(int l,int r,int rt){
if(s<=l&&t>=r){
u[rt].push_back(x);
v[rt].push_back(y);
return;
}
int mid=(l+r)>>;
if(s<=mid)addedge(l,mid,rt<<);
if(t>mid)addedge(mid+,r,rt<<|);
}
void addquery(int l,int r,int rt){
if(l==r){
qu[rt]=x;
qv[rt]=y;
return;
}
qu[rt]|=x;
int mid=(l+r)>>;
if(t<=mid)addquery(l,mid,rt<<);
else addquery(mid+,r,rt<<|);
}
void solve(int l,int r,int rt){
if(!qu[rt])return;
for(int i=;i<(int)u[rt].size();i++)mergeset(u[rt][i],v[rt][i],stk[rt]);
if(l==r)printf(findroot(qu[rt])==findroot(qv[rt])?"Y\n":"N\n");
else{
int mid=(l+r)>>;
solve(l,mid,rt<<);
solve(mid+,r,rt<<|);
}
if(!stk[rt].empty())for(int i=(int)stk[rt].size()-;i>=;i--)prt[stk[rt][i]]=stk[rt][i];
}
int findroot(int x){
while(prt[x]!=x)x=prt[x];
return x;
}
void mergeset(int x,int y,vector<int>&a){
x=findroot(x);y=findroot(y);
if(x==y)return;
if(randint()&)swap(x,y);
prt[x]=y;
a.push_back(x);
}
不知道该加什么分类了，反正是对时间建线段树，加到CDQ分治里算了……