题目很好明白，然后实现很神奇。首先如果考虑并查集的话，对于删边和加边操作我们无法同时进行。然后暴力分块的话，复杂度是O(n sqrt n) ，不是很优。于是看了题解，发现了线段树的神奇用途。

我们维护每个矩形四个顶点的六个变量，分别是：

g[0]：表示第一行左右端点的连通性。

g[1]：表示第二行左右端点的连通性。

g[2]：左上端点和左下端点的连通性。

g[3]：右上端点和右下端点的连通性。

g[4]：左上端点和右下端点的连通性。

g[5]：左下端点和右上端点的连通性。

这六个变量做好之后就可以合并矩形了。同样是这六个变量，合并的时候需要费点事，考虑一下各种情况。

最后需要的一点就是可能出现的特殊情况，这样的怎么办？

我们考虑全面即可，查询的时候不光查询一个区间，还需要查询两头的区间，然后判断是否会出现这种情况，就是我写的solve函数里面判断答案的后三种情况。 ——by VANE

#include
     
      using namespace std;const int N=100005;struct node{
   bool g[6];};int n;node s[5],t[N*4];bool m[N*4];int calc(int x,int y){
   return x*(n-1)+y;}void build(int rt,int l,int r){    if(l==r) {t[rt]=s[0];return;}    int mid=l+r>>1;    build(rt<<1,l,mid);    build(rt<<1|1,mid+1,r);}node merge(node a,node b,bool x,bool y){    node c;    c.g[0]=(a.g[0]&&x&&b.g[0])||(a.g[4]&&y&&b.g[5]);    c.g[1]=(a.g[1]&&y&&b.g[1])||(a.g[5]&&x&&b.g[4]);    c.g[2]=(a.g[2])||(a.g[0]&&x&&b.g[2]&&y&&a.g[1]);    c.g[3]=(b.g[3])||(b.g[0]&&x&&a.g[3]&&y&&b.g[1]);    c.g[4]=(a.g[0]&&x&&b.g[4])||(a.g[4]&&y&&b.g[1]);    c.g[5]=(b.g[0]&&x&&a.g[5])||(b.g[5]&&y&&a.g[1]);    return c;}void insert(int rt,int l,int r,int x,int y,int xx,int yy,bool c){    int mid=l+r>>1;    if(x==xx&&y==mid)    {        m[calc(x,y)]=c;        t[rt]=merge(t[rt<<1],t[rt<<1|1],m[calc(0,mid)],m[calc(1,mid)]);        return;    }    else if(x!=xx&&l==r){t[rt]=s[c];return;}    if(y<=mid) insert(rt<<1,l,mid,x,y,xx,yy,c);    if(y>mid) insert(rt<<1|1,mid+1,r,x,y,xx,yy,c);    t[rt]=merge(t[rt<<1],t[rt<<1|1],m[calc(0,mid)],m[calc(1,mid)]);}node query(int rt,int l,int r,int ll,int rr){    int mid=r+l>>1;    if(l>=ll&&r<=rr) return t[rt];    if(rr<=mid)return query(rt<<1,l,mid,ll,rr);    if(ll>mid) return query(rt<<1|1,mid+1,r,ll,rr);    return merge(query(rt<<1,l,mid,ll,rr),query(rt<<1|1,mid+1,r,ll,rr),m[calc(0,mid)],m[calc(1,mid)]);}void solve(int x,int y,int xx,int yy){    bool ans;    s[2]=query(1,1,n,1,y);    s[3]=query(1,1,n,y,yy);    s[4]=query(1,1,n,yy,n);    if(x==xx) ans=(s[3].g[x])||(s[2].g[3]&&s[3].g[4+x^1])||(s[4].g[2]&&s[3].g[4+x])||(s[2].g[3]&&s[4].g[2]&&s[3].g[x^1]);    else ans=(s[3].g[4+x])||(s[2].g[3]&&s[3].g[x^1])||(s[4].g[2]&&s[3].g[x])||(s[2].g[3]&&s[3].g[4+x^1]&&s[4].g[2]);    if(ans) puts("Y");    else puts("N");    }int main(){    scanf("%d",&n);    s[0]=(node){
   1,1,0,0,0,0};    s[1]=(node){
   1,1,1,1,1,1};    memset(t,0,sizeof t);    memset(m,0,sizeof m);    build(1,1,n);    char ch[6];scanf("%s",ch);    while(ch[0]!='E')    {        int x,y,xx,yy;scanf("%d%d%d%d",&x,&y,&xx,&yy);        if(y>yy) swap(x,xx),swap(y,yy);        x--;xx--;        if(ch[0]=='O') insert(1,1,n,x,y,xx,yy,1);        else if(ch[0]=='C') insert(1,1,n,x,y,xx,yy,0);        else solve(x,y,xx,yy);        scanf("%s",ch);    }}