首页 > 代码库 > [BZOJ 1018][SHOI2008]堵塞的交通traffic（线段树）
[BZOJ 1018][SHOI2008]堵塞的交通traffic（线段树）
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
Solution
线段树维护连通性
a数组表示矩形左上与右上，左上与右下，左下与右上，左下与右下分别是否联通
b数组表示矩形左端和右端各自是否上下相连
这种情况完全可以直接查询两点间的矩形对不对
然而如果路线绕了一个圈…O O
这时候就可以用上b数组了，查询该矩形（指两点间的矩形）以左的所有部分是否能使得左端的上下两个点联通、以右的所有部分是否能使得右端的上下两个点联通
然后分类讨论啊啥的
（一开始只维护了a，想用一些奇怪的方法，写着写着发现不太对，改改改改改…）
代码写的不是很优雅，某些细节十分鸡肋…可能是因为改了太多次
#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>#define MAXN 100005#define Min(a,b) (a<b?a:b)using namespace std;int c;bool col[MAXN],row1[MAXN],row2[MAXN];struct Node{ int l,r; bool a[2][2]; bool b[2]; Node(){l=r=0;memset(a,0,sizeof(a));memset(b,0,sizeof(0));}}t[4*MAXN];Node operator + (const Node& A,const Node& B){ Node C; C.l=A.l,C.r=B.r; C.a[0][0]=(A.a[0][0]&&B.a[0][0])||(A.a[0][1]&&B.a[1][0]); C.a[0][1]=(A.a[0][0]&&B.a[0][1])||(A.a[0][1]&&B.a[1][1]); C.a[1][0]=(A.a[1][0]&&B.a[0][0])||(A.a[1][1]&&B.a[1][0]); C.a[1][1]=(A.a[1][1]&&B.a[1][1])||(A.a[1][0]&&B.a[0][1]); if(A.b[0]||(C.a[0][0]&&C.a[1][0])||(C.a[0][1]&&C.a[1][1]))C.b[0]=1; else C.b[0]=0; if(B.b[1]||(C.a[0][0]&&C.a[0][1])||(C.a[1][0]&&C.a[1][1]))C.b[1]=1; else C.b[1]=0; return C;}int Read(){ int x=0,f=1;char c=getchar(); while(c<‘0‘||c>‘9‘){ if(c==‘-‘)f=-1;c=getchar(); } while(c>=‘0‘&&c<=‘9‘){ x=x*10+c-‘0‘;c=getchar(); } return x*f;}void Build(int idx,int l,int r){ t[idx].l=l,t[idx].r=r; if(l==r) return; int mid=(l+r)>>1; Build(idx<<1,l,mid); Build(idx<<1|1,mid+1,r);}void Change(int idx,int x){ if(t[idx].l==t[idx].r) { t[idx].a[0][0]=t[idx].a[1][1]=t[idx].a[0][1]=t[idx].a[1][0]=0; if(row1[x])t[idx].a[0][0]=1; if(row2[x])t[idx].a[1][1]=1; if(col[x]) t[idx].a[0][1]|=t[idx].a[1][1],t[idx].a[1][0]|=t[idx].a[0][0]; if(col[x+1]) t[idx].a[0][1]|=t[idx].a[0][0],t[idx].a[1][0]|=t[idx].a[1][1]; if(col[x]&&col[x+1]) t[idx].a[0][0]|=t[idx].a[1][1],t[idx].a[1][1]|=t[idx].a[0][0]; t[idx].b[0]=col[t[idx].l],t[idx].b[1]=col[t[idx].l+1]; if((t[idx].a[0][0]&&t[idx].a[1][0])||(t[idx].a[0][1]&&t[idx].a[1][1]))t[idx].b[0]=1; if((t[idx].a[0][0]&&t[idx].a[0][1])||(t[idx].a[1][0]&&t[idx].a[1][1]))t[idx].b[1]=1; return; } int mid=(t[idx].l+t[idx].r)>>1; if(x<=mid)Change(idx<<1,x); else Change(idx<<1|1,x); t[idx]=t[idx<<1]+t[idx<<1|1];}Node Ask(int idx,int x,int y){ if(x>y)return Node(); if(t[idx].l>=x&&t[idx].r<=y) return t[idx]; int mid=(t[idx].l+t[idx].r)>>1; if(y<=mid) return Ask(idx<<1,x,y); else if(x>mid) return Ask(idx<<1|1,x,y); else return Ask(idx<<1,x,y)+Ask(idx<<1|1,x,y);}int main(){ c=Read(); for(int i=1;i<=c;i++)col[i]=0; for(int i=1;i<c;i++)row1[i]=row2[i]=0; Build(1,1,c-1); while(1) { char opt[10];int r1,c1,r2,c2; scanf("%s",opt); if(!strcmp(opt,"Exit")) break; r1=Read();c1=Read();r2=Read();c2=Read(); if(!strcmp(opt,"Open")) { if(r1==r2) { if(c1>c2)swap(c1,c2); if(r1==1)row1[c1]=1; else row2[c1]=1; Change(1,c1); } else if(c1==c2) { col[c1]=1; if(c1-1>0)Change(1,c1-1); if(c1<c)Change(1,c1); } } else if(!strcmp(opt,"Close")) { if(r1==r2) { if(c1>c2)swap(c1,c2); if(r1==1)row1[c1]=0; else row2[c1]=0; Change(1,c1); } else if(c1==c2) { col[c1]=0; if(c1-1>0)Change(1,c1-1); if(c1<c)Change(1,c1); } } else if(!strcmp(opt,"Ask")) { if(c1>c2)swap(c1,c2),swap(r1,r2); r1--;r2--; Node x=Ask(1,1,c1-1),y=Ask(1,c2,c-1),z=Ask(1,c1,c2-1); bool flag=0; if(c1==c2&&(r1==r2||x.b[1]||y.b[0]))flag=1; for(int i=0;i<=1;i++) for(int j=0;j<=1;j++) { if((i==r1||x.b[1])&&(j==r2||y.b[0])&&(z.a[i][j])) flag=1; } if(flag) printf("Y\n"); else printf("N\n"); } } return 0;}
[BZOJ 1018][SHOI2008]堵塞的交通traffic（线段树）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。