=== ===
這里放傳送門
=== ===
題解
這題有毒。。。。據說zyf2000寫了7k代碼結果T了然后又寫了一個。。。
考慮把每個小矩形看做序列中的一個元素，然后對每個區間維護六個量，如下圖所示（媽呀這可怕的分辨率）： 
線段樹里面每一個元素的含義就是在當前節點管轄的矩形序列內部是否存在一條和x0（或其它編號）等價的路徑。比如線段樹中代表y0的元素為true就代表存在一條從這個區間的左上角走到這個區間的左下角的路徑。并且注意到這個東西是可以合并的，也就是說如果把一排小矩形構成的序列以mid為界（這里mid是指兩個點構成的一條豎直的線而不是一個小矩形）分成兩部分，從序列的左端走到右端或從右端走到左端必然會經過mid這條線，那么就可以左右子樹合并來得到父親的值。
舉個例子來說，如果要遞推當前節點的x0，有兩種方法，一是經過mid這條線段的上端點，一是經過mid這條線段的下端點。第一種情況要求左右子樹的x0都聯通，第二種情況要求左子樹的z0和右子樹的z1聯通。
如果是線段樹的葉子節點的話就只能手動枚舉每一種情況了。。。比如上面那個圖如果要求x0聯通，一種方法是AB那條路直接就是通的，還有一種方法是先走y0再走z1，或者y0->x1->y1，或者z0->y1，或者z0->x1->z1。其他的部分情況也超級多啊一定要想全。。。
注意因為線段樹數組里表示的是連通性，而有些時候Close操作的改動可能比較麻煩，舉個例子來說，如果在一個單位矩形中聯通了x0，y0和x1三條邊，那么通過UPD過程會把它所有的6個域都置成true，因為四個點中任意兩個都能相互到達。而如果下一步去掉了y0邊，按理說這時只有x0和x1能聯通了，但線段樹中去掉y0以后剩下的5個域都是true，程序會理解為有5條邊都聯通，然后把對于y0的修改覆蓋掉。于是就另開了一個數組存了不加遞推的原始的邊的情況，在修改的時候一并維護。
查詢操作也非常麻煩。。因為[x..y]這一段的連通性可能不止與[x..y]這一段路徑有關，可能它會上別的地方去繞一圈再回來，簡單來說就是可以直接到達，也可以從左邊拐出序列，也可以從右邊拐出序列，也可以左右同時拐出序列。一條路徑最多有四種不同的走法，都要考慮進去。舉例來說，如果矩形序列[left..right]的x0要聯通，那么一種方法是直接在序列內部從左上角走到右上角，一種方法是先從區間[1..left-1]的右上角走到右下角，即順著y1邊走，然后再從[left..right]的x1邊走，然后從[left..right]的y1邊走到終點，還有一種方法是先順著[left..right]的y0邊走，然后走x1邊，然后順著[right+1..c]的y0邊走等等。
反正這題就是有毒。。。
代碼
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int c,cnt;char o[10];struct tree{ bool b[3][2]; tree(){memset(b,false,sizeof(b));} void UPD(tree g);}t[500010],ans,org[100010];void tree::UPD(tree g){//通過邊的信息枚舉單位矩形的聯通狀況 b[0][0]=g.b[0][0]||(g.b[1][0]&&g.b[2][1])||(g.b[1][0]&&g.b[0][1]&&g.b[1][1])||(g.b[2][0]&&g.b[1][1])||(g.b[2][0]&&g.b[0][1]&&g.b[2][1]); b[0][1]=g.b[0][1]||(g.b[1][0]&&g.b[2][0])||(g.b[1][0]&&g.b[0][0]&&g.b[1][1])||(g.b[2][1]&&g.b[1][1])||(g.b[2][1]&&g.b[0][0]&&g.b[2][0]); b[1][0]=g.b[1][0]||(g.b[2][0]&&g.b[0][1])||(g.b[2][0]&&g.b[1][1]&&g.b[2][1])||(g.b[0][0]&&g.b[2][1])||(g.b[0][0]&&g.b[1][1]&&g.b[0][1]); b[1][1]=g.b[1][1]||(g.b[2][1]&&g.b[0][1])||(g.b[2][1]&&g.b[1][0]&&g.b[2][0])||(g.b[0][0]&&g.b[2][0])||(g.b[0][0]&&g.b[1][0]&&g.b[0][1]); b[2][0]=g.b[2][0]||(g.b[0][0]&&g.b[1][1])||(g.b[0][0]&&g.b[2][1]&&g.b[0][1])||(g.b[1][0]&&g.b[0][1])||(g.b[1][0]&&g.b[2][1]&&g.b[1][1]); b[2][1]=g.b[2][1]||(g.b[1][0]&&g.b[0][0])||(g.b[1][0]&&g.b[2][0]&&g.b[1][1])||(g.b[0][1]&&g.b[1][1])||(g.b[0][1]&&g.b[2][0]&&g.b[0][0]);}void update(tree &tr,tree lc,tree rc){ tr.b[0][0]=(lc.b[0][0]&&rc.b[0][0])||(lc.b[2][0]&&rc.b[2][1]); tr.b[0][1]=(lc.b[0][1]&&rc.b[0][1])||(lc.b[2][1]&&rc.b[2][0]); tr.b[1][0]=lc.b[1][0]||(lc.b[0][0]&&lc.b[0][1]&&rc.b[1][0]); tr.b[1][1]=rc.b[1][1]||(rc.b[0][0]&&rc.b[0][1]&&lc.b[1][1]); tr.b[2][0]=(lc.b[0][0]&&rc.b[2][0])||(lc.b[2][0]&&rc.b[0][1]); tr.b[2][1]=(lc.b[2][1]&&rc.b[0][0])||(lc.b[0][1]&&rc.b[2][1]);}void change(int i,int l,int r,int u,int x,int y,int v){ if (l==r){ org[l].b[x][y]=v;//注意：直接修改的只有org數組 t[i].UPD(org[l]); return; } int mid=(l+r)>>1; if (u<=mid) change(i<<1,l,mid,u,x,y,v); else change((i<<1)+1,mid+1,r,u,x,y,v); update(t[i],t[i<<1],t[(i<<1)+1]);}tree ask(int i,int l,int r,int left,int right){ tree ans[4]; int cnt=0; if ((left<=l)&&(right>=r)) return t[i]; int mid=(l+r)>>1; if (left<=mid){ ans[2]=ask(i<<1,l,mid,left,right);cnt+=1; }//注意用cnt變量記錄訪問信息 if (right>mid){ ans[3]=ask((i<<1)+1,mid+1,r,left,right);cnt+=2; } if (cnt==3){//只有兩半區間都訪問過才合并 update(ans[1],ans[2],ans[3]); return ans[1]; }else return ans[cnt+1];}bool query(int left,int right,int x,int y){ ans=ask(1,1,c,left,right); return ans.b[x][y];}int main(){ scanf("%d",&c);--c; scanf("%s",o); while (o[0]!='E'){ int r1,c1,r2,c2; scanf("%d%d%d%d",&r1,&c1,&r2,&c2); if ((o[0]=='O')||(o[0]=='C')){ int dlt,x,y,num=min(c1,c2); if ((r1==1)&&(r2==1)) x=y=0; if ((r1==2)&&(r2==2)) {x=0;y=1;}//如果是橫向邊，找到要修改的編號 if (o[0]=='O') dlt=1; else dlt=0; if (c1!=c2) change(1,1,c,num,x,y,dlt); if (c1==c2) if (c1==c+1) change(1,1,c,c,1,1,dlt); else if (c1==1) change(1,1,c,1,1,0,dlt); else{//注意在修改一條縱向邊的時候會改變兩個矩形，分別是y1和y0域。 change(1,1,c,c1,1,0,dlt); change(1,1,c,c1-1,1,1,dlt); } }else{ if ((r1==r2)&&(c1==c2)){ 偏偏在最后出現的補充說明這種很麻煩的題一定要想清楚再寫要不然會花費大量的時間調試。。 原來我以前寫代碼就這么蠢啊。。。 我還以為是最近才染上總是會把題寫麻煩的毛病呢= =
