有一天，由于某种穿越现象作用，你来到了传说中的小人国。小人国的布局非常奇特，整个国家的交通系统可
以被看成是一个2行C列的矩形网格，网格上的每个点代表一个城市，相邻的城市之间有一条道路，所以总共有2C个
城市和3C-2条道路。 小人国的交通状况非常槽糕。有的时候由于交通堵塞，两座城市之间的道路会变得不连通，
直到拥堵解决，道路才会恢复畅通。初来咋到的你决心毛遂自荐到交通部某份差事，部长听说你来自一个科技高度
发达的世界，喜出望外地要求你编写一个查询应答系统，以挽救已经病入膏肓的小人国交通系统。 小人国的交通
部将提供一些交通信息给你，你的任务是根据当前的交通情况回答查询的问题。交通信息可以分为以下几种格式：
Close r1 c1 r2 c2：相邻的两座城市(r1,c1)和(r2,c2)之间的道路被堵塞了；Open r1 c1 r2 c2：相邻的两座城
市(r1,c1)和(r2,c2)之间的道路被疏通了；Ask r1 c1 r2 c2：询问城市(r1,c1)和(r2,c2)是否连通。如果存在一
条路径使得这两条城市连通，则返回Y，否则返回N；

　　第一行只有一个整数C，表示网格的列数。接下来若干行，每行为一条交通信息，以单独的一行“Exit”作为
结束。我们假设在一开始所有的道路都是堵塞的。我们保证 C小于等于100000，信息条数小于等于100000。

　　对于每个查询，输出一个“Y”或“N”。

题解：JudgeOnline/upload/201604/sol(4).rar

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #define ls node*2

 #define rs node*2+1

 #define M 100010

 using namespace std;

 struct Tree

 {

     bool l,r;//上下

     bool s1,s2;//左上->右上，左下->右下

     bool s3,s4;//左上->右下，左下->右上

     bool half1,half2;//l,r重点M和M+1之间的连通性

 }tr[M<<];

 void build(int node,int l,int r)

 {

     if(l==r)

     {

         tr[node].half1=tr[node].half2=;

         tr[node].s1=tr[node].s2=;

         return;

     }

     int mid=(l+r)/;

     build(ls,l,mid);

     build(rs,mid+,r);

 }

 void update(Tree &now,Tree L,Tree R)

 {

     now.l=L.l | (L.s1 & L.s2 & now.half1 & now.half2 & R.l);

     now.r=R.r | (R.s1 & R.s2 & now.half1 & now.half2 & L.r);

     now.s1=(L.s1 & R.s1 & now.half1) | (L.s3 & R.s4 & now.half2);

     now.s2=(L.s2 & R.s2 & now.half2) | (L.s4 & R.s3 & now.half1);

     now.s3=(L.s3 & R.s2 & now.half2) | (L.s1 & R.s3 & now.half1);

     now.s4=(L.s4 & R.s1 & now.half1) | (L.s2 & R.s4 & now.half2);

 }

 void changer(int node,int l,int r,int ud,int k,int val)

 {

     int mid=(l+r)/;

     if(mid==k)

     {

         if(ud==) tr[node].half1=val;

         else tr[node].half2=val;

         update(tr[node],tr[ls],tr[rs]);

         return;

     }

     if(k<=mid) changer(ls,l,mid,ud,k,val);

     else changer(rs,mid+,r,ud,k,val);

     update(tr[node],tr[ls],tr[rs]);

 }

 void changec(int node,int l,int r,int k,int val)

 {

     if(l==r)

     {

         tr[node].s3=tr[node].s4=val;

         tr[node].l=tr[node].r=val;

         return;

     }

     int mid=(l+r)/;

     if(k<=mid) changec(ls,l,mid,k,val);

     else changec(rs,mid+,r,k,val);

     update(tr[node],tr[ls],tr[rs]);

 }

 Tree query(int node,int l,int r,int l1,int r1)

 {

     int mid=(l+r)/;

     if(l1<=l&&r1>=r) return tr[node];

     if(r1<=mid) return query(ls,l,mid,l1,r1);

     else if(l1>mid) return query(rs,mid+,r,l1,r1);

     else

     {

         Tree res=tr[node];

         update(res,query(ls,l,mid,l1,r1),query(rs,mid+,r,l1,r1));

         return res;

     }

 }

 int main()

 {

     int n;

     scanf("%d",&n); build(,,n);

     while()

     {

         char s[];

         int r1,r2,c1,c2;

         scanf("%s",s);

         if(s[]=='E') break;

         scanf("%d%d%d%d",&r1,&c1,&r2,&c2);

         if(c1>c2) swap(c1,c2),swap(r1,r2);

         if(s[]=='O')

         {

             if(r1==r2) changer(,,n,r1,c1,);

             else changec(,,n,c1,);

         }

         else if(s[]=='C')

         {

             if(r1==r2) changer(,,n,r1,c1,);

             else changec(,,n,c1,);

         }

         else

         {

             Tree l=query(,,n,,c1),x=query(,,n,c1,c2),r=query(,,n,c2,n);

             bool flag;

             if(r1== && r2==) flag=x.s1 | (l.r & x.s4) | (r.l & x.s3) | (l.r & r.l & x.s2);

             if(r1== && r2==) flag=x.s2 | (l.r & x.s3) | (r.l & x.s4) | (l.r & r.l & x.s1);

             if(r1== && r2==) flag=x.s3 | (l.r & x.s2) | (r.l & x.s1) | (l.r & r.l & x.s4);

             if(r1== && r2==) flag=x.s4 | (l.r & x.s1) | (r.l & x.s2) | (l.r & r.l & x.s3);

             puts(flag?"Y":"N");

         }

     }

     return ;

 }