有一天，由于某种穿越现象作用，你来到了传说中的小人国。小人国的布局非常奇特，整个国家的交通系统可
以被看成是一个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

  1 #include<iostream>  2 #include<algorithm>  3 #include<cstring>  4 #include<cstdio>  5 using namespace std;  6 const int mxn=100010;  7 int read(){  8     int x=0,f=1;char ch=getchar();  9     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 10     while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 11     return x*f; 12 } 13 struct node{ 14     int s[6]; 15 }t[mxn<<2],bas[2]; 16 int id[2][mxn],ict; 17 int mp[mxn]; 18 #define ls rt<<1 19 #define rs rt<<1|1 20 inline node merge(const node &a,const node &b,int mid){ 21     node ans; 22     int x=mp[id[0][mid]],y=mp[id[1][mid]]; 23     ans.s[0]=(a.s[0]&x&b.s[0])|(a.s[4]&y&b.s[5]); 24     ans.s[1]=(a.s[1]&y&b.s[1])|(a.s[5]&x&b.s[4]); 25     ans.s[2]= a.s[2] |(a.s[0]&x&b.s[2]&y&a.s[1]); 26     ans.s[3]= b.s[3] |(b.s[0]&x&a.s[3]&y&b.s[1]); 27     ans.s[4]=(a.s[4]&y&b.s[1])|(a.s[0]&x&b.s[4]); 28     ans.s[5]=(a.s[1]&y&b.s[5])|(a.s[5]&x&b.s[0]); 29     return ans; 30 } 31 void Build(int l,int r,int rt){ 32     if(l==r){t[rt]=bas[0];return;} 33     int mid=(l+r)>>1; 34     Build(l,mid,ls);Build(mid+1,r,rs); 35     return; 36 } 37 void update(int x1,int x2,int y1,int y2,int v,int l,int r,int rt){ 38     if(l==r && x1!=x2 && y1==y2){ 39         t[rt]=bas[v];//该列上下联通  40         return; 41     } 42     int mid=(l+r)>>1; 43     if(x1==x2 && y1==mid){ 44         mp[id[x1][y1]]=v; 45         t[rt]=merge(t[ls],t[rs],mid); 46         return; 47     } 48     //  49     if(y1<=mid) 50         update(x1,x2,y1,y2,v,l,mid,ls); 51     else update(x1,x2,y1,y2,v,mid+1,r,rs); 52     t[rt]=merge(t[ls],t[rs],mid); 53     return; 54 } 55 node query(int L,int R,int l,int r,int rt){ 56     if(L<=l && r<=R)return t[rt]; 57     int mid=(l+r)>>1; 58     if(R<=mid)return query(L,R,l,mid,ls); 59     else if(L>mid)return query(L,R,mid+1,r,rs); 60         else return merge(query(L,mid,l,mid,ls),query(mid+1,R,mid+1,r,rs),mid); 61 } 62 int m; 63 int ask(int x1,int y1,int x2,int y2){ 64     node L=query(1,y1,1,m,1); 65     node R=query(y2,m,1,m,1); 66     node M=query(y1,y2,1,m,1); 67     if(x1==x2){ 68         return M.s[x1] || ( (!x1) && ((L.s[3]&M.s[5]) || (M.s[4]&R.s[2])) ) || 69                           ( (x1) && ( (L.s[3]&M.s[4]) || (M.s[5]&R.s[2]) )) || 70                           (M.s[!x1]&L.s[3]&R.s[2]); 71     } 72     else if((!x1) && x2){ 73         return M.s[4] | (L.s[3]&M.s[1]) | (M.s[0]&R.s[2]) | (L.s[3]&R.s[2]&M.s[5]); 74     } 75     else{ 76         return M.s[5] | (L.s[3]&M.s[0]) | (M.s[1]&R.s[2]) | (L.s[3]&R.s[2]&M.s[4]); 77     } 78 } 79 #undef ls 80 #undef rs 81 int main(){ 82     int i,j; 83     m=read(); 84     for(i=0;i<=1;i++) 85         for(j=1;j<=m;j++) 86             id[i][j]=++ict; 87     // 88     bas[0]=(node){1,1,0,0,0,0}; 89     bas[1]=(node){1,1,1,1,1,1}; 90     Build(1,m,1); 91     char op[5]; 92     int x1,y1,x2,y2; 93     while(1){ 94         scanf("%s",op); 95         if(op[0]==‘E‘)break; 96         x1=read();y1=read();x2=read();y2=read(); 97         --x1;--x2;// 98         if(y1>y2)swap(x1,x2),swap(y1,y2); 99         switch(op[0]){100             case ‘C‘:{101                 update(x1,x2,y1,y2,0,1,m,1);102                 break;103             }104             case ‘O‘:{105                 update(x1,x2,y1,y2,1,1,m,1);106                 break;107             }108             case ‘A‘:{109                 int ans=ask(x1,y1,x2,y2);110                 ans?puts("Y"):puts("N");111                 break;112             }113         }114     }115     return 0;116 }

  1 #include<iostream>  2 #include<algorithm>  3 #include<cstring>  4 #include<cstdio>  5 using namespace std;  6 const int mxn=100010;  7 int read(){  8     int x=0,f=1;char ch=getchar();  9     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 10     while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 11     return x*f; 12 } 13 struct node{ 14     int s[6]; 15 }t[mxn<<2],bas[2]; 16 int id[2][mxn],ict; 17 int mp[mxn]; 18 #define ls rt<<1 19 #define rs rt<<1|1 20 inline node merge(const node &a,const node &b,int mid){ 21     node ans; 22     int x=mp[id[0][mid]],y=mp[id[1][mid]]; 23 //    printf("mid:%d %d %d x:%d y:%d\n",mid,id[0][mid],id[1][mid],x,y); 24     ans.s[0]=(a.s[0]&x&b.s[0])|(a.s[4]&y&b.s[5]); 25     ans.s[1]=(a.s[1]&y&b.s[1])|(a.s[5]&x&b.s[4]); 26     ans.s[2]= a.s[2] |(a.s[0]&x&b.s[2]&y&a.s[1]); 27     ans.s[3]= b.s[3] |(b.s[0]&x&a.s[3]&y&b.s[1]); 28     ans.s[4]=(a.s[4]&y&b.s[1])|(a.s[0]&x&b.s[4]); 29     ans.s[5]=(a.s[1]&y&b.s[5])|(a.s[5]&x&b.s[0]); 30     return ans; 31 } 32 void Build(int l,int r,int rt){ 33     if(l==r){t[rt]=bas[0];return;} 34     int mid=(l+r)>>1; 35     Build(l,mid,ls);Build(mid+1,r,rs); 36     return; 37 } 38 void update(int x1,int x2,int y1,int y2,int v,int l,int r,int rt){ 39     if(l==r && x1!=x2 && y1==y2){ 40         t[rt]=bas[v];//该列上下联通  41         return; 42     } 43     int mid=(l+r)>>1; 44     if(x1==x2 && y1==mid){ 45 //        printf("y1:%d y2:%d l:%d r:%d rt:%d\n",y1,y2,l,r,rt); 46         mp[id[x1][y1]]=v; 47 //        printf("id:%d mp:%d\n",id[x1][y1],mp[id[x1][y1]]); 48         t[rt]=merge(t[ls],t[rs],mid); 49 //        printf("%d %d %d %d %d %d\n",t[rt].s[0],t[rt].s[1],t[rt].s[2],t[rt].s[3],t[rt].s[4],t[rt].s[5]); 50         return; 51     } 52     //  53     if(y1<=mid) 54         update(x1,x2,y1,y2,v,l,mid,ls); 55     else update(x1,x2,y1,y2,v,mid+1,r,rs); 56     t[rt]=merge(t[ls],t[rs],mid); 57     return; 58 } 59 node query(int L,int R,int l,int r,int rt){ 60     if(L<=l && r<=R)return t[rt]; 61     int mid=(l+r)>>1; 62     if(R<=mid)return query(L,R,l,mid,ls); 63     else if(L>mid)return query(L,R,mid+1,r,rs); 64         else return merge(query(L,mid,l,mid,ls),query(mid+1,R,mid+1,r,rs),mid); 65 } 66 int m; 67 int ask(int x1,int y1,int x2,int y2){ 68     node L=query(1,y1,1,m,1); 69     node R=query(y2,m,1,m,1); 70     node M=query(y1,y2,1,m,1); 71     if(x1==x2){ 72         return M.s[x1] || ( (!x1) && ((L.s[3]&M.s[5]) || (M.s[4]&R.s[2])) ) || 73                           ( (x1) && ( (L.s[3]&M.s[4]) || (M.s[5]&R.s[2]) )) || 74                           (M.s[!x1]&L.s[3]&R.s[2]); 75     } 76     else if((!x1) && x2){ 77         return M.s[4] | (L.s[3]&M.s[1]) | (M.s[0]&R.s[2]) | (L.s[3]&R.s[2]&M.s[5]); 78     } 79     else{ 80         return M.s[5] | (L.s[3]&M.s[0]) | (M.s[1]&R.s[2]) | (L.s[3]&R.s[2]&M.s[4]); 81     } 82 } 83 #undef ls 84 #undef rs 85 int main(){ 86 //    freopen("bzoj_1018.in","r",stdin); 87 //    freopen("bzoj_1018.out","w",stdout); 88     int i,j; 89     m=read(); 90     for(i=0;i<=1;i++) 91         for(j=1;j<=m;j++) 92             id[i][j]=++ict; 93     // 94     bas[0]=(node){1,1,0,0,0,0}; 95     bas[1]=(node){1,1,1,1,1,1}; 96     Build(1,m,1); 97     char op[5]; 98     int x1,y1,x2,y2; 99     while(1){100         scanf("%s",op);101         if(op[0]==‘E‘)break;102         x1=read();y1=read();x2=read();y2=read();103         --x1;--x2;//104         if(y1>y2)swap(x1,x2),swap(y1,y2);105         switch(op[0]){106             case ‘C‘:{107                 update(x1,x2,y1,y2,0,1,m,1);108                 break;109             }110             case ‘O‘:{111                 update(x1,x2,y1,y2,1,1,m,1);112                 break;113             }114             case ‘A‘:{115                 int ans=ask(x1,y1,x2,y2);116                 ans?puts("Y"):puts("N");117                 break;118             }119         }120     }121     return 0;122 }