描述
http://www.lydsy.com/JudgeOnline/problem.php?id=1018
\(2*n\)的距形,起初没有边相连,之后有三种操作:
1.加边.
2.删边.
3.询问某两个点是否联通.
分析
这题太神了...
用线段树维护连通性...
放弃解释清楚了...
#include <bits/stdc++.h>
using namespace std; const int maxn=1e5+;
int n,cnt;
char s[];
bool A[maxn][];
struct node{
bool a[][];
node(){
a[][]=a[][]=a[][]=a[][]=false;
}
bool* operator [] (int id){return a[id];}
}a[maxn<<];
struct Segment_tree{
node merge(bool *a,node x,node y){
node t;
t[][]=(x[][]&a[]&y[][])|(x[][]&a[]&y[][]);
t[][]=(x[][]&a[]&y[][])|(x[][]&a[]&y[][]);
t[][]=(x[][]&a[]&y[][])|(x[][]&a[]&y[][]);
t[][]=(x[][]&a[]&y[][])|(x[][]&a[]&y[][]);
return t;
}
void build_tree(int l,int r,int k){
if(l==r){a[k][][]=a[k][][]=true;return;}
int mid=l+(r-l)/;
build_tree(l,mid,k<<); build_tree(mid+,r,k<<|);
}
void update(int l,int r,int k,int pos,bool op,bool dir){
if(l==r){
if(dir) a[k][][]=a[k][][]=op;//c
return;
}
int mid=l+(r-l)/;
if(!dir&&pos==mid){//r
a[k]=merge(A[mid],a[k<<],a[k<<|]);
return;
}
if(pos<=mid) update(l,mid,k<<,pos,op,dir);
else update(mid+,r,k<<|,pos,op,dir);
a[k]=merge(A[mid],a[k<<],a[k<<|]);
}
void _get_right(int l,int r,int k,int &pos,node &t,bool dir){
if(l==r) return;
int mid=l+(r-l)/;
node tmp=merge(A[l-],t,a[k<<]);
if(tmp[dir][]||tmp[dir][]) pos=mid, t=tmp, _get_right(mid+,r,k<<|,pos,t,dir);
else _get_right(l,mid,k<<,pos,t,dir);
}
void _get_left(int l,int r,int k,int &pos,node &t,bool dir){
if(l==r) return;
int mid=l+(r-l)/;
node tmp=merge(A[r],a[k<<|],t);
if(tmp[][dir]||tmp[][dir]) pos=mid+,t=tmp, _get_left(l,mid,k<<,pos,t,dir);
else _get_left(mid+,r,k<<|,pos,t,dir);
}
void get_right(int l,int r,int k,int &pos,node &t,bool dir){
if(l==r) {t=a[k];return;}
int mid=l+(r-l)/;
if(pos>mid) get_right(mid+,r,k<<|,pos,t,dir);
else{
get_right(l,mid,k<<,pos,t,dir);
if(pos!=mid) return;
node tmp=merge(A[mid],t,a[k<<|]);
if(tmp[dir][]||tmp[dir][]) pos=r,t=tmp;
else _get_right(mid+,r,k<<|,pos,t,dir);
}
}
void get_left(int l,int r,int k,int &pos,node &t,bool dir){
if(l==r) {t=a[k];return;}
int mid=l+(r-l)/;
if(pos<=mid) get_left(l,mid,k<<,pos,t,dir);
else{
get_left(mid+,r,k<<|,pos,t,dir);
if(pos!=mid+) return;
node tmp=merge(A[mid],a[k<<],t);
if(tmp[][dir]||tmp[][dir]) pos=l,t=tmp;
else _get_left(l,mid,k<<,pos,t,dir);
}
}
node get_ans(int l,int r,int k,int x,int y){
if(l==x&&r==y) return a[k];
int mid=l+(r-l)/;
if(y<=mid) return get_ans(l,mid,k<<,x,y);
if(x>mid) return get_ans(mid+,r,k<<|,x,y);
return merge(A[mid],get_ans(l,mid,k<<,x,mid),get_ans(mid+,r,k<<|,mid+,y));
}
}t;
void update(int x1,int y1,int x2,int y2,bool op){
if(x1==x2){//r
if(y1>y2) swap(y1,y2);
A[y1][x1]=op;
t.update(,n,,y1,op,false);
}
else t.update(,n,,y1,op,true);//c
}
void query(int x1,int y1,int x2,int y2){
if(y1>y2) swap(x1,x2), swap(y1,y2);
node tmp1;
t.get_left(,n,,y1,tmp1,x1);
x1=tmp1[][x1]?:;
node tmp2;
t.get_right(,n,,y2,tmp2,x2);
x2=tmp2[x2][]?:;
node tmp=t.get_ans(,n,,y1,y2);
puts(tmp[x1][x2]?"Y":"N"); }
int main(){
int x1,y1,x2,y2;
scanf("%d",&n);
t.build_tree(,n,);
while(true){
scanf("%s",s);
if(s[]=='C') scanf("%d%d%d%d",&x1,&y1,&x2,&y2), update(x1-,y1,x2-,y2,false);
else if(s[]=='O') scanf("%d%d%d%d",&x1,&y1,&x2,&y2), update(x1-,y1,x2-,y2,true);
else if(s[]=='A') scanf("%d%d%d%d",&x1,&y1,&x2,&y2), query(x1-,y1,x2-,y2);
else if(s[]=='E') break;
}
return ;
}
1018: [SHOI2008]堵塞的交通traffic
Time Limit: 3 Sec Memory Limit: 162 MB
Submit: 2747 Solved: 914
[Submit][Status][Discuss]
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
Open 1 1 1 2
Open 1 2 2 2
Ask 1 1 2 2
Ask 2 1 2 2
Exit
Sample Output
N