描述
\(2*n\)的距形,起初没有边相连,之后有三种操作:
1.加边.
2.删边.
3.询问某两个点是否联通.
分析
这题太神了...
用线段树维护连通性...
放弃解释清楚了...
1 #include2 using namespace std; 3 4 const int maxn=1e5+5; 5 int n,cnt; 6 char s[10]; 7 bool A[maxn][2]; 8 struct node{ 9 bool a[2][2]; 10 node(){ 11 a[0][0]=a[0][1]=a[1][0]=a[1][1]=false; 12 } 13 bool* operator [] (int id){ return a[id];} 14 }a[maxn<<4]; 15 struct Segment_tree{ 16 node merge(bool *a,node x,node y){ 17 node t; 18 t[0][0]=(x[0][0]&a[0]&y[0][0])|(x[0][1]&a[1]&y[1][0]); 19 t[0][1]=(x[0][0]&a[0]&y[0][1])|(x[0][1]&a[1]&y[1][1]); 20 t[1][0]=(x[1][0]&a[0]&y[0][0])|(x[1][1]&a[1]&y[1][0]); 21 t[1][1]=(x[1][1]&a[1]&y[1][1])|(x[1][0]&a[0]&y[0][1]); 22 return t; 23 } 24 void build_tree(int l,int r,int k){ 25 if(l==r){a[k][0][0]=a[k][1][1]=true;return;} 26 int mid=l+(r-l)/2; 27 build_tree(l,mid,k<<1); build_tree(mid+1,r,k<<1|1); 28 } 29 void update(int l,int r,int k,int pos,bool op,bool dir){ 30 if(l==r){ 31 if(dir) a[k][0][1]=a[k][1][0]=op;//c 32 return; 33 } 34 int mid=l+(r-l)/2; 35 if(!dir&&pos==mid){ //r 36 a[k]=merge(A[mid],a[k<<1],a[k<<1|1]); 37 return; 38 } 39 if(pos<=mid) update(l,mid,k<<1,pos,op,dir); 40 else update(mid+1,r,k<<1|1,pos,op,dir); 41 a[k]=merge(A[mid],a[k<<1],a[k<<1|1]); 42 } 43 void _get_right(int l,int r,int k,int &pos,node &t,bool dir){ 44 if(l==r) return; 45 int mid=l+(r-l)/2; 46 node tmp=merge(A[l-1],t,a[k<<1]); 47 if(tmp[dir][0]||tmp[dir][1]) pos=mid, t=tmp, _get_right(mid+1,r,k<<1|1,pos,t,dir); 48 else _get_right(l,mid,k<<1,pos,t,dir); 49 } 50 void _get_left(int l,int r,int k,int &pos,node &t,bool dir){ 51 if(l==r) return; 52 int mid=l+(r-l)/2; 53 node tmp=merge(A[r],a[k<<1|1],t); 54 if(tmp[0][dir]||tmp[1][dir]) pos=mid+1,t=tmp, _get_left(l,mid,k<<1,pos,t,dir); 55 else _get_left(mid+1,r,k<<1|1,pos,t,dir); 56 } 57 void get_right(int l,int r,int k,int &pos,node &t,bool dir){ 58 if(l==r) {t=a[k];return;} 59 int mid=l+(r-l)/2; 60 if(pos>mid) get_right(mid+1,r,k<<1|1,pos,t,dir); 61 else{ 62 get_right(l,mid,k<<1,pos,t,dir); 63 if(pos!=mid) return; 64 node tmp=merge(A[mid],t,a[k<<1|1]); 65 if(tmp[dir][0]||tmp[dir][1]) pos=r,t=tmp; 66 else _get_right(mid+1,r,k<<1|1,pos,t,dir); 67 } 68 } 69 void get_left(int l,int r,int k,int &pos,node &t,bool dir){ 70 if(l==r) {t=a[k];return;} 71 int mid=l+(r-l)/2; 72 if(pos<=mid) get_left(l,mid,k<<1,pos,t,dir); 73 else{ 74 get_left(mid+1,r,k<<1|1,pos,t,dir); 75 if(pos!=mid+1) return; 76 node tmp=merge(A[mid],a[k<<1],t); 77 if(tmp[0][dir]||tmp[1][dir]) pos=l,t=tmp; 78 else _get_left(l,mid,k<<1,pos,t,dir); 79 } 80 } 81 node get_ans(int l,int r,int k,int x,int y){ 82 if(l==x&&r==y) return a[k]; 83 int mid=l+(r-l)/2; 84 if(y<=mid) return get_ans(l,mid,k<<1,x,y); 85 if(x>mid) return get_ans(mid+1,r,k<<1|1,x,y); 86 return merge(A[mid],get_ans(l,mid,k<<1,x,mid),get_ans(mid+1,r,k<<1|1,mid+1,y)); 87 } 88 }t; 89 void update(int x1,int y1,int x2,int y2,bool op){ 90 if(x1==x2){ //r 91 if(y1>y2) swap(y1,y2); 92 A[y1][x1]=op; 93 t.update(1,n,1,y1,op,false); 94 } 95 else t.update(1,n,1,y1,op,true);//c 96 } 97 void query(int x1,int y1,int x2,int y2){ 98 if(y1>y2) swap(x1,x2), swap(y1,y2); 99 node tmp1;100 t.get_left(1,n,1,y1,tmp1,x1);101 x1=tmp1[0][x1]?0:1;102 node tmp2;103 t.get_right(1,n,1,y2,tmp2,x2);104 x2=tmp2[x2][0]?0:1;105 node tmp=t.get_ans(1,n,1,y1,y2);106 puts(tmp[x1][x2]?"Y":"N");107 108 }109 int main(){110 int x1,y1,x2,y2;111 scanf("%d",&n);112 t.build_tree(1,n,1);113 while(true){114 scanf("%s",s);115 if(s[0]=='C') scanf("%d%d%d%d",&x1,&y1,&x2,&y2), update(x1-1,y1,x2-1,y2,false);116 else if(s[0]=='O') scanf("%d%d%d%d",&x1,&y1,&x2,&y2), update(x1-1,y1,x2-1,y2,true);117 else if(s[0]=='A') scanf("%d%d%d%d",&x1,&y1,&x2,&y2), query(x1-1,y1,x2-1,y2);118 else if(s[0]=='E') break;119 }120 return 0;121 }
1018: [SHOI2008]堵塞的交通traffic
Time Limit: 3 Sec Memory Limit: 162 MBSubmit: 2747 Solved: 914[][][]Description
有一天，由于某种穿越现象作用，你来到了传说中的小人国。小人国的布局非常奇特，整个国家的交通系统可
以被看成是一个2行C列的矩形网格，网格上的每个点代表一个城市，相邻的城市之间有一条道路，所以总共有2C个 城市和3C-2条道路。 小人国的交通状况非常槽糕。有的时候由于交通堵塞，两座城市之间的道路会变得不连通， 直到拥堵解决，道路才会恢复畅通。初来咋到的你决心毛遂自荐到交通部某份差事，部长听说你来自一个科技高度 发达的世界，喜出望外地要求你编写一个查询应答系统，以挽救已经病入膏肓的小人国交通系统。 小人国的交通 部将提供一些交通信息给你，你的任务是根据当前的交通情况回答查询的问题。交通信息可以分为以下几种格式： 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
第一行只有一个整数C，表示网格的列数。接下来若干行，每行为一条交通信息，以单独的一行“Exit”作为
结束。我们假设在一开始所有的道路都是堵塞的。我们保证 C小于等于100000，信息条数小于等于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
题解：