动态图的连通性当然是可以用LCT维护的。但这相当的不优美，毕竟这样做没有用到任何该图的性质，LCT自带的大常数也会使其跑得非常慢。
考虑用线段树维护区间左右端四个点之间各自的连通性（仅经过该区间内路径）。查询时考虑几种绕来绕去的情况。
剩下的是大讨论。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } #define N 100010 int n; bool r[N][2]; struct data{int L,R;bool f[6],w[2];//0 u 1 d 2 l 3 r 4 z 5 f }tree[N<<2]; int whichop(int x,int y,int u,int v) { if (y==v) return 2; if (x==u) return x; return x==0?5:4; } void build(int k,int l,int r) { tree[k].L=l,tree[k].R=r; if (l==r) {tree[k].f[0]=tree[k].f[1]=1;return;} else tree[k].w[0]=tree[k].w[1]=1; int mid=l+r>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); } data merge(data x,data y) { data v;v.L=x.L,v.R=y.R; v.w[0]=x.w[0]||y.w[0]||!r[x.R][0]; v.w[1]=x.w[1]||y.w[1]||!r[x.R][1]; v.f[0]=x.f[0]&&y.f[0]&&r[x.R][0]||x.f[5]&&y.f[4]&&r[x.R][1]; v.f[1]=x.f[1]&&y.f[1]&&r[x.R][1]||x.f[4]&&y.f[5]&&r[x.R][0]; v.f[2]=x.f[2]||x.f[0]&&r[x.R][0]&&r[x.R][1]&&y.f[2]; v.f[3]=y.f[3]||y.f[0]&&r[x.R][0]&&r[x.R][1]&&x.f[3]; v.f[4]=x.f[4]&&r[x.R][0]&&y.f[0]||x.f[1]&&r[x.R][1]&&y.f[4]; v.f[5]=x.f[5]&&r[x.R][1]&&y.f[1]||x.f[0]&&r[x.R][0]&&y.f[5]; return v; } void modifyrow(int k,int x) { if (tree[k].L==tree[k].R) return; if (tree[k].L+1==tree[k].R) {tree[k]=merge(tree[k<<1],tree[k<<1|1]);return;} int mid=tree[k].L+tree[k].R>>1; if (x<mid) modifyrow(k<<1,x); else if (x>mid) modifyrow(k<<1|1,x); tree[k]=merge(tree[k<<1],tree[k<<1|1]); } void modifyline(int k,int x,int op) { if (tree[k].L==tree[k].R) { tree[k].f[0]=tree[k].f[1]=1; tree[k].f[2]=tree[k].f[3]=tree[k].f[4]=tree[k].f[5]=op; return; } int mid=tree[k].L+tree[k].R>>1; if (x<=mid) modifyline(k<<1,x,op); else modifyline(k<<1|1,x,op); tree[k]=merge(tree[k<<1],tree[k<<1|1]); } data query(int k,int l,int r) { if (tree[k].L==l&&tree[k].R==r) return tree[k]; int mid=tree[k].L+tree[k].R>>1; if (r<=mid) return query(k<<1,l,r); else if (l>mid) return query(k<<1|1,l,r); else return merge(query(k<<1,l,mid),query(k<<1|1,mid+1,r)); } bool isempty(int k,int L,int R,int x) { if (tree[k].L==L&&tree[k].R==R) return !tree[k].w[x]; int mid=tree[k].L+tree[k].R>>1; if (R<=mid) return isempty(k<<1,L,R,x); else if (L>mid) return isempty(k<<1|1,L,R,x); else return r[tree[k<<1].R][x]&&isempty(k<<1,L,mid,x)&&isempty(k<<1|1,mid+1,R,x); } int queryleft(int k,int p,int x) { if (tree[k].L==tree[k].R) return tree[k].L; int mid=tree[k].L+tree[k].R>>1; if (p<=mid) return queryleft(k<<1,p,x); else return isempty(k<<1|1,tree[k<<1|1].L,p,x)&&r[tree[k<<1].R][x]?queryleft(k<<1,tree[k<<1].R,x):queryleft(k<<1|1,p,x); } int queryright(int k,int p,int x) { if (tree[k].L==tree[k].R) return tree[k].L; int mid=tree[k].L+tree[k].R>>1; if (p<=mid) return isempty(k<<1,p,tree[k<<1].R,x)&&r[tree[k<<1].R][x]?queryright(k<<1|1,tree[k<<1|1].L,x):queryright(k<<1,p,x); else return queryright(k<<1|1,p,x); } int main() { #ifndef ONLINE_JUDGE freopen("bzoj1018.in","r",stdin); freopen("bzoj1018.out","w",stdout); const char LL[]="%I64d "; #else const char LL[]="%lld "; #endif n=read(); build(1,1,n); char c=getchar();while (c<'A'||c>'Z') c=getchar(); while (c!='E') { int x=read(),y=read(),u=read(),v=read(); if (y>v) swap(x,u),swap(y,v);x--,u--; if (c=='O') { if (y==v) modifyline(1,y,1); else r[y][x]=1,modifyrow(1,y); } else if (c=='C') { if (y==v) modifyline(1,y,0); else r[y][x]=0,modifyrow(1,y); } else { y=queryleft(1,y,x); v=queryright(1,v,u); printf(query(1,y,v).f[whichop(x,y,u,v)]?"Y ":"N "); } c=getchar();while (c<'A'||c>'Z') c=getchar(); } return 0; }