对于一个区间四个角的点，可以用线段树记下来它们两两的联通情况
区间[l,r]通过两个子区间[l,m],[m+1,r]来更新，相当于合并[l,m],[m+1,r]，用(m,m+1)这条边来合并
查询a,b答案的话，不仅可以直接从[a,b]区间连通，也有可能从旁边绕了一圈
总之细节很多 懒得写了
升级版：suoi33 诡异的交通
#include<bits/stdc++.h>
#define pa pair<int,int>
#define CLR(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=1e5+; inline ll rd(){
ll x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} struct Node{
bool ll,rr,uu,ud,du,dd;
int c[],l,r;
Node(bool a=,bool b=,bool cr=,bool d=,bool e=,bool f=,int x=,int y=,int i=,int j=){
ll=a,rr=b,uu=cr,ud=d,du=e,dd=f;
l=x,r=y;c[]=i,c[]=j;
}
}t[maxn*];
int N,pct;
bool con[maxn][]; inline void print(Node x){
printf("[%d,%d]->[%d,%d]&[%d,%d]:\n",x.l,x.r,t[x.c[]].l,t[x.c[]].r,t[x.c[]].l,t[x.c[]].r);
// printf("[%d,%d]->%d,%d:\n",x.l,x.r,x.c[0],x.c[1]);
printf("\tUU:%d UD:%d DD:%d DU:%d LL:%d RR:%d\n",x.uu,x.ud,x.dd,x.du,x.ll,x.rr);
}
inline void flash(Node &x){
x.uu|=(x.ud&&x.rr)||(x.ll&&x.du)||(x.ll&&x.dd&&x.rr);
x.dd|=(x.du&&x.rr)||(x.ll&&x.ud)||(x.ll&&x.uu&&x.rr);
x.ud|=(x.uu&&x.rr)||(x.ll&&x.dd)||(x.ll&&x.du&&x.rr);
x.du|=(x.dd&&x.rr)||(x.ll&&x.uu)||(x.ll&&x.ud&&x.rr);
}
Node operator + (Node a,Node b){
Node p;
p.l=a.l,p.r=b.r;
int m=a.r;
p.uu=(a.uu&&con[m][]&&b.uu)||(a.ud&&con[m][]&&b.du);
p.dd=(a.dd&&con[m][]&&b.dd)||(a.du&&con[m][]&&b.ud);
p.ud=(a.uu&&con[m][]&&b.ud)||(a.ud&&con[m][]&&b.dd);
p.du=(a.dd&&con[m][]&&b.du)||(a.du&&con[m][]&&b.uu);
p.ll=a.ll||(a.uu&&con[m][]&&b.ll&&con[m][]&&a.dd);
p.rr=b.rr||(b.uu&&con[m][]&&a.rr&&con[m][]&&b.dd);
flash(p);
// print(p);
return p;
} inline void update(int p){
int l=t[p].c[],r=t[p].c[];
if(l&&r)t[p]=t[t[p].c[]]+t[t[p].c[]];
t[p].c[]=l,t[p].c[]=r;
} void build(int &p,int l,int r){
p=++pct;
if(l==r) t[p]=Node(,,,,,,l,r,,);
else{
int m=l+r>>;
build(t[p].c[],l,m);
build(t[p].c[],m+,r);
update(p);//print(t[p]);
}
} void query(int p,int l,int r,int x,int y,Node &re){
if(x<=l&&r<=y){
if(!re.l&&!re.r) re=t[p];
else re=re+t[p];
}else{
int m=l+r>>;
if(x<=m) query(t[p].c[],l,m,x,y,re);
if(y>=m+) query(t[p].c[],m+,r,x,y,re);
}
} void change1(int p,int l,int r,int x){
if(l<r){
int m=l+r>>;
if(x<=m) change1(t[p].c[],l,m,x);
else change1(t[p].c[],m+,r,x);
update(p);
// print(t[p]);
}
}
void change2(int p,int l,int r,int x,bool b){
if(l==r){
t[p].ud=t[p].du=t[p].ll=t[p].rr=b;
}else{
int m=l+r>>;
if(x<=m) change2(t[p].c[],l,m,x,b);
else change2(t[p].c[],m+,r,x,b);
update(p);
}
} inline void solve1(int r1,int c1,int r2,int c2,bool b){
if(r1==r2){
c1=min(c1,c2);
con[c1][r1-]=b;
change1(,,N,c1);
}else{
change2(,,N,c1,b);
}
} inline bool solve2(int r1,int c1,int r2,int c2){
Node a,b,c;
if(c1>c2) swap(r1,r2),swap(c1,c2);
query(,,N,,c1,a);
query(,,N,c1,c2,b);
query(,,N,c2,N,c);
//print(a);print(b);print(c);
b.ll|=a.rr,b.rr|=c.ll;
flash(b);
if(r1==){
if(r2==) return b.ud;
else return b.uu;
}else{
if(r2==) return b.dd;
else return b.du;
}
} int main(){
//freopen("","r",stdin);
int i,j,k;
N=rd();
// for(i=1;i<N;i++) con[i][0]=con[i][1]=1;
build(i,,N);
while(){
char s[];
scanf("%s",s);
if(s[]=='E') break;
int a=rd(),b=rd(),c=rd(),d=rd();
if(s[]=='O'){
solve1(a,b,c,d,);
}else if(s[]=='C'){
solve1(a,b,c,d,);
}else{
bool x=solve2(a,b,c,d);
if(x) printf("Y\n");
else printf("N\n");
}
}
return ;
}