Time Limit:?3 Sec??Memory Limit:?162 MB
Submit:?3458??Solved:?1158

Description

　　有一天，由于某種穿越現(xiàn)象作用，你來到了傳說中的小人國。小人國的布局非常奇特，整個國家的交通系統(tǒng)可
以被看成是一個2行C列的矩形網(wǎng)格，網(wǎng)格上的每個點(diǎn)代表一個城市，相鄰的城市之間有一條道路，所以總共有2C個
城市和3C-2條道路。 小人國的交通狀況非常槽糕。有的時候由于交通堵塞，兩座城市之間的道路會變得不連通，
直到擁堵解決，道路才會恢復(fù)暢通。初來咋到的你決心毛遂自薦到交通部某份差事，部長聽說你來自一個科技高度
發(fā)達(dá)的世界，喜出望外地要求你編寫一個查詢應(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

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

Sample Output

Y
N

HINT

?題解：JudgeOnline/upload/201604/sol(4).rar

Source

?

線段樹 腦洞題

學(xué)自http://blog.csdn.net/huanghongxun/article/details/51213009

?

exm？線段樹怎么還能這么玩兒啊？

矩形只有兩行，顯然（根本不）可以想到把兩行并到一起處理。

對于一個矩形，我們記錄它左上角、左下角、右上角、右下角四個方塊之間的連通情況，共有6種。

如上圖： S0：上方連通 ? S1：下方連通 ?S2：左上和左下連通 ?S3：右上和右下連通 ? S4：左下和右上連通 ? S5:左上和右下連通

在所維護(hù)矩形只有一列的時候，只剩下兩種情況：上下不連通（只有s0和s1為true），上下連通（全為true）

?在改變某一列連通狀態(tài)時，我們從左區(qū)間提取出它最右面的一列，利用該列和左右區(qū)間的所有s信息就可以算出大區(qū)間的s信息。

?用線段樹可以方便地維護(hù)

在改變同一行的相鄰兩列的連通狀態(tài)時，也可以類似地維護(hù)

?

查詢兩格(x1,y1) (x2,y2)是否聯(lián)通的時候，由于可能會存在“先往反方向走出[y1,y2]區(qū)間，再繞回來，使得兩點(diǎn)聯(lián)通”這種情況，所以不能只查[y1,y2]區(qū)間，而要查詢[1,y1],[y1,y2],[y2,m]三段區(qū)間來判斷答案。

?

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];//該列上下聯(lián)通 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 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/SilverNebula/p/6869707.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的Bzoj1018 [SHOI2008]堵塞的交通traffic的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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