故意堵塞交通怎么處理，[SHOI2008]堵塞的交通traffic

線段樹維護連通性。。。

通過分析我們可以發現，一個城市到另一個城市一共只有很少的幾種情況

所以我們可以維護這個 2*X 矩形

故意堵塞交通怎么處理？判斷其 從左上角到左下角

　　　　 左上角到右上角

　　　　 左上角到右下角

　　　　 左下角到右上角

　　　　 左下角到右下角

交警疏通道路堵塞電話？　　　　 右上角到右下角

　　　　　　　　　　　 的連通性

通過得到的連通性再判斷即可

呆碼：

#include<iostream>
#include<cstdio>
using namespace std;struct asd{bool luru,ldrd;bool lurd,ldru;bool luld,rurd;bool self[3];
} a[100010*4];
// l:left ; r:right ; u:up ; d:down
// 表示能否從一個角到另一個角 int r1,r2,c1,c2,n;inline asd pushup(asd x,asd y)
{asd ans;ans.luru=ans.ldrd=0;ans.lurd=ans.ldru=0;ans.luld=ans.rurd=0;ans.self[1]=y.self[1],ans.self[2]=y.self[2];if((x.luru && x.self[1] && y.luru) || (x.lurd && x.self[2] && y.ldru)) ans.luru=1;if((x.ldrd && x.self[2] && y.ldrd) || (x.ldru && x.self[1] && y.lurd)) ans.ldrd=1;if((x.luru && x.self[1] && y.lurd) || (x.lurd && x.self[2] && y.ldrd)) ans.lurd=1;if((x.ldrd && x.self[2] && y.ldru) || (x.ldru && x.self[1] && y.luru)) ans.ldru=1;if((x.luld) || (x.luru && x.self[1] && y.luld && x.self[2] && x.ldrd)) ans.luld=1;if((y.rurd) || (y.luru && x.self[1] && x.rurd && x.self[2] && y.ldrd)) ans.rurd=1;return ans;
}inline void build(int rt,int l,int r)
{if(l==r){a[rt].luru=a[rt].ldrd=1;return;}int mid=l+r>>1;build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);a[rt]=pushup(a[rt<<1],a[rt<<1|1]);
}inline void change1(int rt,int l,int r,int L,int k)
{if(l==r){a[rt].lurd=a[rt].ldru=a[rt].luld=a[rt].rurd=k;return;}int mid=l+r>>1;if(L<=mid) change1(rt<<1,l,mid,L,k);else change1(rt<<1|1,mid+1,r,L,k);a[rt]=pushup(a[rt<<1],a[rt<<1|1]);
}inline void change2(int rt,int l,int r,int L,int y,int k)
{if(l==r){a[rt].self[y]=k;return;}int mid=l+r>>1;if(L<=mid) change2(rt<<1,l,mid,L,y,k);else change2(rt<<1|1,mid+1,r,L,y,k);a[rt]=pushup(a[rt<<1],a[rt<<1|1]);
}inline asd query(int rt,int l,int r,int L,int R)
{if(L<=l && r<=R) { return a[rt]; }int mid=l+r>>1;asd ans1,ans2;bool left=0,right=0;if(L<=mid) ans1=query(rt<<1,l,mid,L,R),left=1;if(R>mid) ans2=query(rt<<1|1,mid+1,r,L,R),right=1;if(left==1 && right==1) return pushup(ans1,ans2);else return left==1 ? ans1 : ans2;
}inline bool check()
{if(c1>c2) { swap(c1,c2); swap(r1,r2); }asd pre=query(1,1,n,1,c1);asd now=query(1,1,n,c1,c2);asd nxt=query(1,1,n,c2,n);if(r1==r2){if(r1==1 && ((now.luru) || (pre.rurd && now.ldru) || (nxt.luld && now.lurd) || (pre.rurd && now.ldrd && nxt.luld))) return 1;if(r1==2 && ((now.ldrd) || (pre.rurd && now.lurd) || (nxt.luld && now.ldru) || (pre.rurd && now.luru && nxt.luld))) return 1;}else{if(r1==1 && ((now.lurd) || (pre.rurd && now.ldrd) || (nxt.luld && now.luru) || (pre.rurd && now.ldru && nxt.luld))) return 1;if(r1==2 && ((now.ldru) || (pre.rurd && now.luru) || (nxt.luld && now.ldrd) || (pre.rurd && now.lurd && nxt.luld))) return 1;}return 0;
}int main()
{scanf("%d",&n);build(1,1,n);while(1){char ch[10]; scanf("%s",ch);if(ch[0]=='E') break;scanf("%d%d%d%d",&r1,&c1,&r2,&c2);if(ch[0]=='O'){if(c1==c2) change1(1,1,n,c1,1);else change2(1,1,n,min(c1,c2),r1,1);}if(ch[0]=='C'){if(c1==c2) change1(1,1,n,c1,0);else change2(1,1,n,min(c1,c2),r1,0);}if(ch[0]=='A'){if(check()) printf("Y\n");else printf("N\n");}}return 0;
}

?