题目链接：
题目大意： 一个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。题解：
线段树。。 线段树上的一个点维护相邻四个点的连通状况(就是[0][x],[1][x],[0][x+1],[1][x+1]这四个点)，即以四个点为一个单位。 每次修改就更新被修改的两格所在的单位点的连通情况，然后从线段树的最底层更新上去。注意，修改上下两格的话要维护两个点。 询问的时候，首先判断两个点能否直接在它们所在区间里即[c1,c2-1]中相连。（为什么是c2-1?因为这个表示的是线段树里的区间。比如线段树的总区间只是[1,n-1]。因为四个点为一个单位点啊） 如果在区间里不能连通，那么就看看左边的点能不能从它的左边绕过来，右边的点能不能从右边绕过来，三种情况各自判断一下：1、左边绕回来后能否到右边的点；2、右边绕回来后能否到左边的点；3、左右都绕回来后能否相互到达。然后。。我就打了5k。。。心力交瘁。。细节啊细节！！！
#include#include #include #include #include using namespace std;#define maxn 200010//0-左上下 1-上上 2-上下 3-下上 4-下下 5-右上下struct node{ bool cn[6]; node() { memset(cn,0,sizeof(cn));}}tr[maxn];int len,rt;int llc[maxn],rrc[maxn];bool bo[2][maxn][2],bh[maxn];//0-左 1-右node upd(node lc,node rc){ node ret; if (lc.cn[0] || (lc.cn[1] && lc.cn[4] && rc.cn[0])) ret.cn[0]=true; if ((lc.cn[1] && rc.cn[1]) || (lc.cn[2] && rc.cn[3])) ret.cn[1]=true; if ((lc.cn[1] && rc.cn[2]) || (lc.cn[2] && rc.cn[4])) ret.cn[2]=true; if ((lc.cn[4] && rc.cn[3]) || (lc.cn[3] && rc.cn[1])) ret.cn[3]=true; if ((lc.cn[4] && rc.cn[4]) || (lc.cn[3] && rc.cn[2])) ret.cn[4]=true; if (rc.cn[5] || (lc.cn[5] && rc.cn[1] && rc.cn[4])) ret.cn[5]=true; return ret;}void based(int now,int x){ memset(tr[now].cn,0,sizeof(tr[now].cn)); if (bh[x] || (bo[0][x][1] && bh[x+1] && bo[1][x][1])) tr[now].cn[0]=true; if (bo[0][x][1] || (bh[x] && bh[x+1] && bo[1][x][1])) tr[now].cn[1]=true; if ((bo[0][x][1] && bh[x+1]) || (bh[x] && bo[1][x][1])) tr[now].cn[2]=true; if ((bh[x] && bo[0][x][1]) || (bo[1][x][1] && bh[x+1])) tr[now].cn[3]=true; if (bo[1][x][1] || (bh[x] && bh[x+1] && bo[0][x][1])) tr[now].cn[4]=true; if (bh[x+1] || (bo[0][x+1][0] && bh[x] && bo[1][x][1])) tr[now].cn[5]=true;}void change(int &now,int L,int R,int x){ if (!now) now=++len; if (L==R) {based(now,x);return;} int mid=(L+R)>>1; if (x<=mid) change(llc[now],L,mid,x); else change(rrc[now],mid+1,R,x); tr[now]=upd(tr[llc[now]],tr[rrc[now]]);}node query(int &now,int L,int R,int l,int r){ if (!now) now=++len; if (L==l && R==r) return tr[now]; int mid=(L+R)>>1; if (r<=mid) return query(llc[now],L,mid,l,r); else if (l>mid) return query(rrc[now],mid+1,R,l,r); else { node lc=query(llc[now],L,mid,l,mid); node rc=query(rrc[now],mid+1,R,mid+1,r); return upd(lc,rc); }}int main(){ //freopen("a.in","r",stdin); //freopen("a.out","w",stdout); int n,x1,x2,y1,y2;char s[10]; scanf("%d\n",&n);rt=len=0; memset(bo,false,sizeof(bo)); memset(bh,false,sizeof(bh)); memset(llc,0,sizeof(llc)); memset(rrc,0,sizeof(rrc)); while (1) { scanf("%s",s); if (s[0]=='E') break; if (s[0]=='O') { scanf("%d%d%d%d\n",&x1,&y1,&x2,&y2);x1--;x2--; if (y1>y2) { int tt=x1;x1=x2;x2=tt; tt=y1;y1=y2;y2=tt; } if (y1==y2) { bh[y1]=true; if (y1!=1) change(rt,1,n-1,y1-1); if (y1!=n) change(rt,1,n-1,y1); }else { bo[x1][y1][1]=bo[x2][y2][0]=true; change(rt,1,n-1,y1); } } else if (s[0]=='C') { scanf("%d%d%d%d\n",&x1,&y1,&x2,&y2);x1--;x2--; if (y1>y2) { int tt=x1;x1=x2;x2=tt; tt=y1;y1=y2;y2=tt; } if (y1==y2) { bh[y1]=false; if (y1!=1) change(rt,1,n-1,y1-1); if (y1!=n) change(rt,1,n-1,y1); }else { bo[x1][y1][1]=bo[x2][y2][0]=false; change(rt,1,n-1,y1); } } else { scanf("%d%d%d%d\n",&x1,&y1,&x2,&y2);x1--;x2--; if (y1>y2) { int tt=x1;x1=x2;x2=tt; tt=y1;y1=y2;y2=tt; } if (y1==y2) { node lx;bool bk=false;bk|=bh[y1]; if (y1!=1) {lx=query(rt,1,n-1,1,y1-1);bk|=lx.cn[5];} if (y1!=n) {lx=query(rt,1,n-1,y1,n-1);bk|=lx.cn[0];} if (bk) printf("Y\n"); else printf("N\n"); } else { node lx=query(rt,1,n-1,y1,y2-1); if (lx.cn[x1*2+x2+1]) { printf("Y\n");continue;} node zz,yy; if (y1!=1) zz=query(rt,1,n-1,1,y1-1); if (y2!=n) yy=query(rt,1,n-1,y2,n-1); if (x1==0 && x2==0) { if (y1!=1 && zz.cn[5] && lx.cn[3]) { printf("Y\n");continue;} if (y2!=n && yy.cn[0] && lx.cn[2]) { printf("Y\n");continue;} if (y1!=1 && y2!=n && zz.cn[5] && yy.cn[0] && lx.cn[4]) { printf("Y\n");continue;} printf("N\n");continue; } if (x1==0 && x2==1) { if (y1!=1 && zz.cn[5] && lx.cn[4]) { printf("Y\n");continue;} if (y2!=n && yy.cn[0] && lx.cn[1]) { printf("Y\n");continue;} if (y1!=1 && y2!=n && zz.cn[5] && yy.cn[0] && lx.cn[3]) { printf("Y\n");continue;} printf("N\n");continue; } if (x1==1 && x2==0) { if (y1!=1 && zz.cn[5] && lx.cn[1]) { printf("Y\n");continue;} if (y2!=n && yy.cn[0] && lx.cn[4]) { printf("Y\n");continue;} if (y1!=1 && y2!=n && zz.cn[5] && yy.cn[0] && lx.cn[2]) { printf("Y\n");continue;} printf("N\n");continue; } if (x1==1 && x2==1) { if (y1!=1 && zz.cn[5] && lx.cn[2]) { printf("Y\n");continue;} if (y2!=n && yy.cn[0] && lx.cn[3]) { printf("Y\n");continue;} if (y1!=1 && y2!=n && zz.cn[5] && yy.cn[0] && lx.cn[1]) { printf("Y\n");continue;} printf("N\n");continue; } } } } return 0;}