有一天，由于某种穿越现象作用，你来到了传说中的小人国。小人国的布局非常奇特，整个国家的交通系统可
以被看成是一个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”。
麻烦的一批。先找出一共有几种情况要维护，尤其是不要漏掉先往外走再往里走的蛇皮走位
如果直接去维护某两点之间的路径是什么，是没法维护的。事实上两点之间不管是经历了怎样蛇皮的走位走过来，与我们都无关，我们要维护的只是两点是否联通。对于相邻两列四个点，如图，一共有六种路径，我们需要维护它们。而如何向上合并呢？我们还要维护两个儿子之间是否联通。这些想清楚了剩下的反而简单了，对着图慢慢打就行啦~
代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define ls node*2 5 #define rs node*2+1 6 #define M 100010 7 using namespace std; 8 struct Tree 9 { 10 bool l,r;//上下 11 bool s1,s2;//左上->右上，左下->右下 12 bool s3,s4;//左上->右下，左下->右上 13 bool half1,half2;//l,r重点M和M+1之间的连通性 14 }tr[M<<2]; 15 16 void build(int node,int l,int r) 17 { 18 if(l==r) 19 { 20 tr[node].half1=tr[node].half2=1; 21 tr[node].s1=tr[node].s2=1; 22 return; 23 } 24 int mid=(l+r)/2; 25 build(ls,l,mid); 26 build(rs,mid+1,r); 27 } 28 29 void update(Tree &now,Tree L,Tree R) 30 { 31 now.l=L.l | (L.s1 & L.s2 & now.half1 & now.half2 & R.l); 32 now.r=R.r | (R.s1 & R.s2 & now.half1 & now.half2 & L.r); 33 now.s1=(L.s1 & R.s1 & now.half1) | (L.s3 & R.s4 & now.half2); 34 now.s2=(L.s2 & R.s2 & now.half2) | (L.s4 & R.s3 & now.half1); 35 now.s3=(L.s3 & R.s2 & now.half2) | (L.s1 & R.s3 & now.half1); 36 now.s4=(L.s4 & R.s1 & now.half1) | (L.s2 & R.s4 & now.half2); 37 } 38 39 void changer(int node,int l,int r,int ud,int k,int val) 40 { 41 int mid=(l+r)/2; 42 if(mid==k) 43 { 44 if(ud==1) tr[node].half1=val; 45 else tr[node].half2=val; 46 update(tr[node],tr[ls],tr[rs]); 47 return; 48 } 49 if(k<=mid) changer(ls,l,mid,ud,k,val); 50 else changer(rs,mid+1,r,ud,k,val); 51 update(tr[node],tr[ls],tr[rs]); 52 } 53 54 void changec(int node,int l,int r,int k,int val) 55 { 56 if(l==r) 57 { 58 tr[node].s3=tr[node].s4=val; 59 tr[node].l=tr[node].r=val; 60 return; 61 } 62 int mid=(l+r)/2; 63 if(k<=mid) changec(ls,l,mid,k,val); 64 else changec(rs,mid+1,r,k,val); 65 update(tr[node],tr[ls],tr[rs]); 66 } 67 68 Tree query(int node,int l,int r,int l1,int r1) 69 { 70 int mid=(l+r)/2; 71 if(l1<=l&&r1>=r) return tr[node]; 72 if(r1<=mid) return query(ls,l,mid,l1,r1); 73 else if(l1>mid) return query(rs,mid+1,r,l1,r1); 74 else 75 { 76 Tree res=tr[node]; 77 update(res,query(ls,l,mid,l1,r1),query(rs,mid+1,r,l1,r1)); 78 return res; 79 } 80 } 81 82 int main() 83 { 84 int n; 85 scanf("%d",&n); build(1,1,n); 86 while(1) 87 { 88 char s[10]; 89 int r1,r2,c1,c2; 90 scanf("%s",s); 91 if(s[0]==‘E‘) break; 92 scanf("%d%d%d%d",&r1,&c1,&r2,&c2); 93 if(c1>c2) swap(c1,c2),swap(r1,r2); 94 if(s[0]==‘O‘) 95 { 96 if(r1==r2) changer(1,1,n,r1,c1,1); 97 else changec(1,1,n,c1,1); 98 } 99 else if(s[0]==‘C‘) 100 { 101 if(r1==r2) changer(1,1,n,r1,c1,0); 102 else changec(1,1,n,c1,0); 103 } 104 else 105 { 106 Tree l=query(1,1,n,1,c1),x=query(1,1,n,c1,c2),r=query(1,1,n,c2,n); 107 bool flag; 108 if(r1==1 && r2==1) flag=x.s1 | (l.r & x.s4) | (r.l & x.s3) | (l.r & r.l & x.s2); 109 if(r1==2 && r2==2) flag=x.s2 | (l.r & x.s3) | (r.l & x.s4) | (l.r & r.l & x.s1); 110 if(r1==1 && r2==2) flag=x.s3 | (l.r & x.s2) | (r.l & x.s1) | (l.r & r.l & x.s4); 111 if(r1==2 && r2==1) flag=x.s4 | (l.r & x.s1) | (r.l & x.s2) | (l.r & r.l & x.s3); 112 puts(flag?"Y":"N"); 113 } 114 } 115 return 0; 116 }
原文：https://www.cnblogs.com/Slrslr/p/9545877.html