首页 > 代码库 > BZOJ 1018 线段树维护图的连通性问题
BZOJ 1018 线段树维护图的连通性问题
思路：
我们可以搞一棵线段树
对于一段区间有6种情况需要讨论
左上右下、左上右上、左下右下、左下右上
这四种比较好维护
用左上右下举个例子吧
就是左儿子的左上右下&左区间到右区间下面有路&右儿子的左下右下
或者是左儿子的左上右上&左区间到右区间上面有路&右儿子的左上右下
还有两种 区间的左（右）端点上下能不能联通 需要维护
这种就是左儿子的上下连通或（左上右上&左上右下&左到右两条路都联通&右儿子的上下联通）
（假设c1<c2）
最后要查的是 1->c1 （可以1~c1上下联通再c1[!r1]->c2）
c1->c2（直接联通当然最好）
c2->cn
还有一种是1~c1上下联通&c2~n上下联通&c1[!r1]与c2[!r2]上下联通
4种分类讨论即可
//By SiriusRen#include <cstdio>#include <algorithm>using namespace std;const int N=100050;int map[N][2],map2[N],n,r1,c1,r2,c2,jy;char op[15];struct Node{bool b[2][2],c[2];}tree[N*16];Node push_up(Node L,Node R,int mid){ Node tmp; tmp.b[0][0]=(L.b[0][0]&map[mid][0]&R.b[0][0])|(L.b[0][1]&map[mid][1]&R.b[1][0]); tmp.b[0][1]=(L.b[0][0]&map[mid][0]&R.b[0][1])|(L.b[0][1]&map[mid][1]&R.b[1][1]); tmp.b[1][0]=(L.b[1][0]&map[mid][0]&R.b[0][0])|(L.b[1][1]&map[mid][1]&R.b[1][0]); tmp.b[1][1]=(L.b[1][0]&map[mid][0]&R.b[0][1])|(L.b[1][1]&map[mid][1]&R.b[1][1]); tmp.c[0]=L.c[0]|(L.b[0][0]&map[mid][0]&map[mid][1]&L.b[1][1]&R.c[0]); tmp.c[1]=R.c[1]|(R.b[0][0]&map[mid][0]&map[mid][1]&R.b[1][1]&L.c[1]); return tmp;}void build(int l,int r,int pos){ if(l==r){tree[pos].b[1][1]=tree[pos].b[0][0]=1;return;} int mid=(l+r)>>1,lson=pos<<1,rson=pos<<1|1; build(l,mid,lson),build(mid+1,r,rson);}void insert(int l,int r,int pos,int L,int num,bool v){ if(l==r){ if(num==2)tree[pos].b[0][1]=tree[pos].b[1][0]=tree[pos].c[0]=tree[pos].c[1]=map2[l]=v; else map[l][num]=v;return; } int mid=(l+r)>>1,lson=pos<<1,rson=pos<<1|1; if(mid<L)insert(mid+1,r,rson,L,num,v); else insert(l,mid,lson,L,num,v); tree[pos]=push_up(tree[lson],tree[rson],mid);}Node query(int l,int r,int pos,int L,int R){ if(l>=L&&r<=R)return tree[pos]; int mid=(l+r)>>1,lson=pos<<1,rson=pos<<1|1; if(mid<L)return query(mid+1,r,rson,L,R); else if(mid>=R)return query(l,mid,lson,L,R); else return push_up(query(l,mid,lson,L,R),query(mid+1,r,rson,L,R),mid);}int main(){ scanf("%d",&n),build(1,n,1); while(scanf("%s",op)&&op[0]!=‘E‘){ scanf("%d%d%d%d",&r1,&c1,&r2,&c2),r1--,r2--; if(c1>c2)swap(c1,c2),swap(r1,r2); if(op[0]==‘A‘){ Node a=query(1,n,1,1,c1),b=query(1,n,1,c2,n),c=query(1,n,1,c1,c2); if(c.b[r1][r2]|(a.c[1]&c.b[!r1][r2])|(b.c[0]&c.b[r1][!r2])|(b.c[0]&a.c[1]&c.b[!r1][!r2]))puts("Y"); else puts("N"); } else{ if(r1==r2)jy=(r1==1); else jy=2; insert(1,n,1,c1,jy,op[0]==‘O‘); } }}
BZOJ 1018 线段树维护图的连通性问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。