【題目描述】
BZOJ1018 | SHOI2008-堵塞的交通traffic

　有一天，由于某種穿越現(xiàn)象作用，你來到了傳說中的小人國。小人國的布局非常奇特，整個(gè)國家的交通系統(tǒng)可 以被看成是一個(gè)2行C列的矩形網(wǎng)格，網(wǎng)格上的每個(gè)點(diǎn)代表一個(gè)城市，相鄰的城市之間有一條道路，所以總共有2C個(gè) 城市和3C-2條道路。 小人國的交通狀況非常槽糕。有的時(shí)候由于交通堵塞，兩座城市之間的道路會(huì)變得不連通， 直到擁堵解決，道路才會(huì)恢復(fù)暢通。初來咋到的你決心毛遂自薦到交通部某份差事，部長聽說你來自一個(gè)科技高度 發(fā)達(dá)的世界，喜出望外地要求你編寫一個(gè)查詢應(yīng)答系統(tǒng)，以挽救已經(jīng)病入膏肓的小人國交通系統(tǒng)。 小人國的交通 部將提供一些交通信息給你，你的任務(wù)是根據(jù)當(dāng)前的交通情況回答查詢的問題。交通信息可以分為以下幾種格式： 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

　　第一行只有一個(gè)整數(shù)C，表示網(wǎng)格的列數(shù)。接下來若干行，每行為一條交通信息，以單獨(dú)的一行“Exit”作為 結(jié)束。我們假設(shè)在一開始所有的道路都是堵塞的。我們保證 C小于等于100000，信息條數(shù)小于等于100000。

Output

　　對(duì)于每個(gè)查詢，輸出一個(gè)“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 Exit

Sample Output

Y N

【題目分析】
啊啊啊，我終于在題解的幫助下做出這道有$(e)$意$(xin)$思$(ren)$的題啦，之前看都不想看這道題，可是沒有辦法只能耐著性子看網(wǎng)上的題解，可是題解我覺得他們都覺得自己講的挺詳細(xì)，可是我看完還是一臉懵逼，又不想看代碼。找來找去找了一個(gè)代碼看起來挺好看的一個(gè)博客耐著性子看完后才算是大概理解了。
題目的意思應(yīng)該挺好理解，不過需要注意的是題目中說修改的城市都是相鄰的！！！我剛開始一直沒有注意這個(gè)，覺得這個(gè)題沒法做。
還是區(qū)間問題，要用萬能的線段樹解決的話，主要的問題是維護(hù)什么，不同于一般的線段樹問題大都是一維的，這個(gè)問題是二維的，雖然只有兩行，但是顯然不是以前簡單的區(qū)間就可以的。我們要維護(hù)的是矩形區(qū)間，葉子節(jié)點(diǎn)是一列兩行的沒有寬度的矩形，我們對(duì)于每個(gè)矩形維護(hù)四條邊和兩條對(duì)角線來記錄矩形四個(gè)點(diǎn)之間的連通性關(guān)系。但是如果我們合并兩個(gè)相鄰的矩形，他們之間還有兩條邊，因此我們專門用一個(gè)數(shù)組來記錄每列之間兩條邊的關(guān)系和上下兩個(gè)城市的連通性。我們不妨記這個(gè)數(shù)組為$Link$，$Link[i][0][0]$對(duì)應(yīng)第i列和i+1列第一行之間的連通性，$Link[i][1][1]$對(duì)應(yīng)第i列和i+1列第二行之間的連通性，$Link[i][0][1]$對(duì)應(yīng)第i列第一行與第二行之間的連通性。
然后我們用線段樹維護(hù)區(qū)間的方法維護(hù)整個(gè)區(qū)間，修改兩個(gè)城市之間的關(guān)系的時(shí)候先修改Link數(shù)組，然后根據(jù)Link數(shù)組單點(diǎn)修改。對(duì)于每次查詢操作，我們分別得到$[1,c1],[c1,c2],[c2,n]$三個(gè)區(qū)間的矩形（用一個(gè)區(qū)間查詢），然后根據(jù)這三個(gè)區(qū)間進(jìn)行操作。
具體的看代碼吧，嘿嘿嘿（露出了善$(xie)$良$(e)$）的微笑。
照著大佬的博客敲都wa了四發(fā)，嗚嗚嗚。線段樹忘記開區(qū)間*4了，然后還有一個(gè)數(shù)字寫錯(cuò)了。
【參考博客】
傳送門
【AC代碼】

#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<iostream> #include<cmath> #include<climits> #include<queue> #include<vector> #include<set> #include<map> using namespace std;typedef long long ll; const int INF=0x3f3f3f3f; const int MAXN=1e5+5; struct node {int a1,a2,b1,b2,c1,c2;void init(){a1=a2=b1=b2=c1=c2=0;} }mp[MAXN<<2]; int Link[MAXN][2][2]; int n; char cmd[10]; int r1,c1,r2,c2;node PushUp(node a,node b,int mid) {node c;if(a.a1 || (a.b1&&Link[mid][0][0]&&b.a1&&Link[mid][1][1]&&a.b2))c.a1=1;else c.a1=0;if(b.a2 || (b.b1&&Link[mid][0][0]&&a.a2&&Link[mid][1][1]&&b.b2))c.a2=1;elsec.a2=0;if((a.b1&&Link[mid][0][0]&&b.b1) || (a.c1&&Link[mid][1][1]&&b.c2))c.b1=1;elsec.b1=0;if((a.b2&&Link[mid][1][1]&&b.b2) || (a.c2&&Link[mid][0][0]&&b.c1))c.b2=1;elsec.b2=0;if((a.b1&&Link[mid][0][0]&&b.c1) || (b.b2&&Link[mid][1][1]&&a.c1))c.c1=1;else c.c1=0;if((a.b2&&Link[mid][1][1]&&b.c2) || (b.b1&&Link[mid][0][0]&&a.c2))c.c2=1;else c.c2=0;return c; }void build(int k,int l,int r) {mp[k].init();if(l==r){mp[k].b1=mp[k].b2=1;return;}int mid=(l+r)>>1;build(k<<1,l,mid); build(k<<1|1,mid+1,r);//mp[k]=PushUp(mp[k<<1],mp[k<<1|1],mid); }void Update(int k,int l,int r,int x) {if(l==r && l==x){mp[k].b1=mp[k].b2=1;mp[k].a1=mp[k].a2=mp[k].c1=mp[k].c2=Link[x][0][1];return;}int mid=(l+r)>>1;if(x<=mid) Update(k<<1,l,mid,x);else Update(k<<1|1,mid+1,r,x);mp[k]=PushUp(mp[k<<1],mp[k<<1|1],mid); }void Change(int x) {if(c1==c2){Link[c1][0][1]=x;Update(1,1,n,c1);}else{int c=min(c1,c2);Link[c][r1][r1]=x;Update(1,1,n,c);} }node Query(int k,int l,int r,int L,int R) {if(l>=L && r<=R){return mp[k];}int mid=(l+r)>>1;node ret; ret.init();if(R<=mid) return Query(k<<1,l,mid,L,R);else if(L>mid) return Query(k<<1|1,mid+1,r,L,R);else return PushUp(Query(k<<1,l,mid,L,mid),Query(k<<1|1,mid+1,r,mid+1,R),mid); }void Ask() {if(c1>c2){swap(c1,c2); swap(r1,r2);}node l=Query(1,1,n,1,c1);node mid=Query(1,1,n,c1,c2);node r=Query(1,1,n,c2,n);if(r1==r2){if(r1==0){if(mid.b1 || (l.a2&&mid.c2) || (r.a1&&mid.c1) || (l.a2&&mid.b2&&r.a1)){printf("Y");}else{printf("N");}}else if(r1==1){if(mid.b2 || (l.a2&&mid.c1) || (r.a1&&mid.c2) || (l.a2&&mid.b1&&r.a1)){printf("Y");}else{printf("N");}}}else{if(r1==0){if(mid.c1 || (l.a2&&mid.b2) || (r.a1&&mid.b1) || (l.a2&&mid.c2&&r.a1)){printf("Y");}else{printf("N");}}else if(r1==1){if(mid.c2 || (l.a2&&mid.b1) || (r.a1&&mid.b2) || (l.a2&&mid.c1&&r.a1)){printf("Y");}else{printf("N");}}}printf("\n"); }int main() {scanf("%d",&n);build(1,1,n);while(~scanf("%s",cmd) && cmd[0]!='E'){scanf("%d%d%d%d",&r1,&c1,&r2,&c2);r1--; r2--;if(cmd[0]=='O'){Change(1);}else if(cmd[0]=='C'){Change(0);}else{Ask();}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的BZOJ1018 | SHOI2008-堵塞的交通traffic——线段树维护区间连通性+细节的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。