BZOJ1018: [SHOI2008]堵塞的交通traffic
$n leq 100000$$，$2*n$的网格资磁以下操作：两个相邻点连边；两个相邻点断边；两个点查连通性。
线段树还能这么用也是想不到QAQ
线段树维护一下连通性。一个区间矩形有四个点，六对连通性记一下（其实记四对也行），可以合并。由于修改边是单修，开仨数组记记即可。
查询的时候注意，如果两个点是同一列的那就查以他为右端点和以他为左端点的矩形；如果不是同一列，首先要查他们中间的那块能否使他们连通，但还有一种情况，那就是：
所以再查一下以左边点为右端点的矩形和以右边点为左端点的矩形。
1 //#include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 //#include<time.h> 5 //#include<complex> 6 #include<algorithm> 7 #include<stdlib.h> 8 using namespace std; 9 10 #define LL long long 11 int qread() 12 { 13 char c; int s=0; while ((c=getchar())<'0' || c>'9'); 14 do s=s*10+c-'0'; while ((c=getchar())>='0' && c<='9'); return s; 15 } 16 17 //Pay attention to '-' and LL of qread!!!! 18 19 int n; 20 #define maxn 200011 21 bool uu[maxn],dd[maxn],ss[maxn]; 22 23 struct nnode{bool a[6]; nnode() {memset(a,0,sizeof(a));} }; 24 void combine(nnode &u,nnode v,nnode w) 25 { 26 u.a[0]=(v.a[0] && w.a[0]) || (v.a[4] && w.a[5]); 27 u.a[1]=(v.a[1] && w.a[1]) || (v.a[5] && w.a[4]); 28 u.a[2]=(v.a[2]) || (v.a[0] && w.a[2] && v.a[1]); 29 u.a[3]=(w.a[3]) || (w.a[0] && v.a[3] && w.a[1]); 30 u.a[4]=(v.a[0] && w.a[4]) || (v.a[4] && w.a[1]); 31 u.a[5]=(v.a[1] && w.a[5]) || (v.a[5] && w.a[0]); 32 } 33 34 struct SMT 35 { 36 struct Node{int ls,rs; nnode s;}a[maxn<<1]; 37 int size,n; 38 void up(int x) {combine(a[x].s,a[a[x].ls].s,a[a[x].rs].s);} 39 void build(int &x,int L,int R) 40 { 41 x=++size; 42 if (L==R) return; 43 int mid=(L+R)>>1; 44 build(a[x].ls,L,mid); build(a[x].rs,mid+1,R); 45 } 46 void build() {int x; build(x,1,n);} 47 void clear(int m) {n=m; size=0; build();} 48 int P; 49 void Modify(int x,int L,int R) 50 { 51 if (L==R) 52 { 53 nnode &u=a[x].s; 54 u.a[0]=(uu[P]) || (ss[P] && dd[P] && ss[P+1]); 55 u.a[1]=(dd[P]) || (ss[P] && uu[P] && ss[P+1]); 56 u.a[2]=(ss[P]) || (uu[P] && dd[P] && ss[P+1]); 57 u.a[3]=(uu[P] && ss[P] && dd[P]) || (ss[P+1]); 58 u.a[4]=(uu[P] && ss[P+1]) || (ss[P] && dd[P]); 59 u.a[5]=(uu[P] && ss[P]) || (ss[P+1] && dd[P]); 60 return; 61 } 62 int mid=(L+R)>>1; 63 if (P<=mid) Modify(a[x].ls,L,mid); else Modify(a[x].rs,mid+1,R); 64 up(x); 65 } 66 void modify(int pos) {if (pos<1 || pos>n) return; this->P=pos; Modify(1,1,n);} 67 int ql,qr; 68 nnode Query(int x,int L,int R) 69 { 70 if (ql<=L && R<=qr) return a[x].s; 71 int mid=(L+R)>>1; nnode ans,tmp; bool flag=0; 72 if (ql<=mid) flag=1,ans=Query(a[x].ls,L,mid); 73 if (qr>mid) 74 { 75 if (flag) {tmp=ans; combine(ans,tmp,Query(a[x].rs,mid+1,R));} 76 else ans=Query(a[x].rs,mid+1,R); 77 } 78 return ans; 79 } 80 nnode query(int L,int R) {nnode w; if (L>R) return w; ql=L; qr=R; return Query(1,1,n);} 81 }t; 82 83 int main() 84 { 85 scanf("%d",&n); 86 t.clear(n-1); 87 int x2,y2,x3,y3; char c; 88 while (1) 89 { 90 while ((c=getchar())!='A' && c!='O' && c!='C' && c!='E'); 91 if (c=='E') break; 92 if (c=='A') 93 { 94 x2=qread(); y2=qread(); x3=qread(); y3=qread(); 95 if (y2==y3) 96 { 97 if (t.query(1,y2-1).a[3] || t.query(y2,n-1).a[2]) puts("Y"); 98 else puts("N"); 99 } 100 else 101 { 102 if (y2>y3) y2^=y3^=y2^=y3,x2^=x3^=x2^=x3; 103 int ty=(x2==1 && x3==1)?0:((x2==1 && x3==2)?4:((x2==2 && x3==1)?5:1)); 104 nnode hh=t.query(y2,y3-1); 105 if (hh.a[ty] || (t.query(1,y2-1).a[3] && t.query(y3,n-1).a[2] 106 && (hh.a[0] || hh.a[1] || hh.a[4] || hh.a[5]))) puts("Y"); 107 else puts("N"); 108 } 109 } 110 else if (c=='C') 111 { 112 x2=qread(); y2=qread(); x3=qread(); y3=qread(); 113 if (y2==y3) {ss[y2]=0; t.modify(y2-1); t.modify(y2);} 114 else 115 { 116 if (y2>y3) y2^=y3^=y2^=y3,x2^=x3^=x2^=x3; 117 if (x2==1) {uu[y2]=0; t.modify(y2);} 118 else {dd[y2]=0; t.modify(y2);} 119 } 120 } 121 else if (c=='O') 122 { 123 x2=qread(); y2=qread(); x3=qread(); y3=qread(); 124 if (y2==y3) {ss[y2]=1; t.modify(y2-1); t.modify(y2);} 125 else 126 { 127 if (y2>y3) y2^=y3^=y2^=y3,x2^=x3^=x2^=x3; 128 if (x2==1) {uu[y2]=1; t.modify(y2);} 129 else {dd[y2]=1; t.modify(y2);} 130 } 131 } 132 } 133 return 0; 134 }