1018: [SHOI2008]堵塞的交通traffic
Time Limit: 3 Sec Memory Limit: 162 MBSubmit: 3242 Solved: 1084[][][]Description
有一天，由于某种穿越现象作用，你来到了传说中的小人国。小人国的布局非常奇特，整个国家的交通系统可
以被看成是一个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；Input
第一行只有一个整数C，表示网格的列数。接下来若干行，每行为一条交通信息，以单独的一行“Exit”作为
结束。我们假设在一开始所有的道路都是堵塞的。我们保证 C小于等于100000，信息条数小于等于100000。Output
对于每个查询，输出一个“Y”或“N”。
Sample Input
2 Open 1 1 1 2 Open 1 2 2 2 Ask 1 1 2 2 Ask 2 1 2 2 ExitSample Output
Y N
【分析】
线段树真是太多功能了。
简单说一下：
线段树的点[L,R]维护六个bool，表示[1,L][2,L][1,R][2,R]两两之间的，只在这个区间内的边上走的连通性。
修改的时候从最下面update上去，[L,MID][MID+1,R]两区间合并不用说了吧。。。
询问的时候分成三个区间[1,L-1][L,R][R+1,N]
先问[L,R]之间能不能使他联通，不然，还有三种情况，
三个都判断一下就好了，【我还漏了第三种 TAT
代码好丑：
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 #define Maxn 100010 8 9 char s[110]; 10 11 struct node 12 { 13 int l,r,lc,rc; 14 bool c11,c12,c21,c22,cl,cr; 15 }tr[Maxn*2]; 16 17 bool cn[2][Maxn],cn2[Maxn]; 18 19 void upd(int x) 20 { 21 if(tr[x].l==tr[x].r) return; 22 int lc=tr[x].lc,rc=tr[x].rc; 23 int mid=(tr[x].l+tr[x].r)>>1; 24 tr[x].c11=tr[x].c12=tr[x].c21=tr[x].c22=tr[x].cl=tr[x].cr=0; 25 if(tr[lc].c11&&tr[rc].c11&&cn[0][mid]) tr[x].c11=1; 26 if(tr[lc].c12&&tr[rc].c21&&cn[1][mid]) tr[x].c11=1; 27 28 if(tr[lc].c11&&tr[rc].c12&&cn[0][mid]) tr[x].c12=1; 29 if(tr[lc].c12&&tr[rc].c22&&cn[1][mid]) tr[x].c12=1; 30 31 if(tr[lc].c21&&tr[rc].c11&&cn[0][mid]) tr[x].c21=1; 32 if(tr[lc].c22&&tr[rc].c21&&cn[1][mid]) tr[x].c21=1; 33 34 if(tr[lc].c21&&tr[rc].c12&&cn[0][mid]) tr[x].c22=1; 35 if(tr[lc].c22&&tr[rc].c22&&cn[1][mid]) tr[x].c22=1; 36 37 if((tr[lc].c11&&tr[lc].c22&&tr[rc].cl&&cn[0][mid]&&cn[1][mid])||tr[lc].cl) tr[x].cl=1; 38 if((tr[rc].c11&&tr[rc].c22&&tr[lc].cr&&cn[0][mid]&&cn[1][mid])||tr[rc].cr) tr[x].cr=1; 39 } 40 41 int tot; 42 int build(int l,int r) 43 { 44 int x=++tot; 45 tr[x].l=l;tr[x].r=r; 46 tr[x].c11=tr[x].c12=tr[x].c21=tr[x].c22=tr[x].cl=tr[x].cr=0; 47 if(l!=r) 48 { 49 int mid=(l+r)>>1; 50 tr[x].lc=build(l,mid); 51 tr[x].rc=build(mid+1,r); 52 } 53 else tr[x].lc=tr[x].rc=0,tr[x].c11=tr[x].c22=tr[x].cl=tr[x].cr=1; 54 return x; 55 } 56 57 void change(int x,int l,int r) 58 { 59 if(tr[x].l==tr[x].r) 60 { 61 if(cn2[l]) tr[x].c12=tr[x].c21=tr[x].cl=tr[x].cr=1; 62 else tr[x].c12=tr[x].c21=tr[x].cl=tr[x].cr=0; 63 return; 64 } 65 int mid=(tr[x].l+tr[x].r)>>1; 66 if(r<=mid) change(tr[x].lc,l,r); 67 else if(l>mid) change(tr[x].rc,l,r); 68 else 69 { 70 change(tr[x].lc,l,mid); 71 change(tr[x].rc,mid+1,r); 72 } 73 upd(x); 74 } 75 76 bool a11,a12,a21,a22,al,ar; 77 void query(int x,int l,int r) 78 { 79 if(tr[x].l==l&&tr[x].r==r) 80 { 81 a11=tr[x].c11; 82 a12=tr[x].c12; 83 a21=tr[x].c21; 84 a22=tr[x].c22; 85 al=tr[x].cl;ar=tr[x].cr; 86 return; 87 } 88 int mid=(tr[x].l+tr[x].r)>>1; 89 if(r<=mid) query(tr[x].lc,l,r); 90 else if(l>mid) query(tr[x].rc,l,r); 91 else 92 { 93 bool b11,b12,b21,b22,bl,br,c11,c12,c21,c22,cl,cr; 94 query(tr[x].lc,l,mid);b11=a11;b12=a12;b21=a21;b22=a22;bl=al;br=ar; 95 query(tr[x].rc,mid+1,r);c11=a11;c12=a12;c21=a21;c22=a22;cl=al;cr=ar; 96 a11=a12=a21=a22=al=ar=0; 97 if(b11&&c11&&cn[0][mid]) a11=1; 98 if(b12&&c21&&cn[1][mid]) a11=1; 99 100 if(b11&&c12&&cn[0][mid]) a12=1;101 if(b12&&c22&&cn[1][mid]) a12=1;102 103 if(b21&&c11&&cn[0][mid]) a21=1;104 if(b22&&c21&&cn[1][mid]) a21=1;105 106 if(b21&&c12&&cn[0][mid]) a22=1;107 if(b22&&c22&&cn[1][mid]) a22=1;108 if((b11&&b22&&cl&&cn[0][mid]&&cn[1][mid])||bl) al=1;109 if((c11&&c22&&br&&cn[0][mid]&&cn[1][mid])||cr) ar=1;110 }111 }112 113 int main()114 {115 int n;116 scanf("%d",&n);117 tot=0;118 build(1,n);119 for(int i=1;i<=n;i++) cn[0][i]=cn[1][i]=cn2[i]=0;120 while(1)121 {122 scanf("%s",s);123 if(s[0]=='E') break;124 int r1,c1,r2,c2;125 scanf("%d%d%d%d",&r1,&c1,&r2,&c2);126 // if(c1>c2) swap(c1,c2);127 if(c1>c2||(c1==c2&&r1>r2))128 {129 swap(r1,r2);swap(c1,c2);130 // int tt;131 // tt=r1,r1=r2,r1=tt;132 // tt=c1,c1=c2,c2=tt;133 }134 if(s[0]=='O')135 {136 if(r1==r2) cn[r1-1][c1]=1;137 else cn2[c1]=1;138 change(1,c1,c2);139 }140 else if(s[0]=='C')141 {142 if(r1==r2) cn[r1-1][c1]=0;143 else cn2[c1]=0;144 change(1,c1,c2);145 }146 else147 {148 if(r1==r2&&c1==c2) {printf("Y\n");continue;}149 a11=a12=a21=a22=al=ar=0;150 query(1,c1,c2);151 if(r1==1&&r2==1&&a11) printf("Y\n");152 else if(r1==1&&r2==2&&a12) printf("Y\n");153 else if(r1==2&&r2==1&&a21) printf("Y\n");154 else if(r1==2&&r2==2&&a22) printf("Y\n");155 else156 {157 bool b11,b12,b21,b22;158 b11=a11;b12=a12;b21=a21;b22=a22;159 bool ok=0,p1=0,p2=0;160 if(cn[0][c1-1]&&cn[1][c1-1])161 {162 a11=a12=a21=a22=al=ar=0;163 query(1,1,c1-1);if(ar)164 if((r2==1&&(b11||b21))||(r2==2&&(b12||b22))) {ok=1;printf("Y\n");}165 if(ar) p1=1;166 }167 if(!ok&&cn[0][c2]&&cn[1][c2]&&c2
2017-03-08 13:27:45