BZOJ 1018 [SHOI2008]堵塞的交通traffic

1018: [SHOI2008]堵塞的交通traffic

Time Limit: 3 Sec  Memory Limit: 162 MB
Submit: 2247  Solved: 706
[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”作为结束。我们假设在一开始所有的道路都是堵塞的。 对30%测试数据,我们保证C小于等于1000,信息条数小于等于1000; 对100%测试数据,我们保证 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

 

Source

题解:一道码农题。。。

先考虑一维的情况:很显然窝萌可以用一个线段树来维护连通性,但二维的怎么就想不到呢。。。QAQ。。。

二维同样是满足区间加法的,那窝萌要做的就是使劲讨论就行了。。。码农题嘛。。。

对我的变量进行一下解释:大家看键盘上qwas这这四个键,按方向打出来就是一个方框内的连通性辣~

看了很多题解都用的是神马s[2],v[2],w[2]的,感觉自己好机智呀!

BZOJ 1018 [SHOI2008]堵塞的交通traffic

代码们:

 #include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#define PAU putchar(' ')
#define ENT putchar('\n')
#define CH for(int d=0;d<2;d++) if(ch[d])
#define lson x->ch[0],L,M
#define rson x->ch[1],M+1,R
using namespace std;
const int maxn=+,maxnode=+;
struct info{bool qa,ws,qw,as,qs,aw;info(){qw=as=true;}void init(){qa=ws=qs=aw=false;qw=as=true;return;}};
struct side{bool qw,as,qa,ws;}op[maxn];
struct node{node*ch[];info a;}seg[maxnode],*nodecnt=seg,*root;
int T,n,r1,r2,c1,c2,dx[]={-,,},dy[]={,,},ql,qr,pos,cv;char s[];
void build(node*&x=root,int L=,int R=n){
x=nodecnt++;if(L==R)return;int M=L+R>>;build(lson);build(rson);return;
}
void merge(info&u,info l,info r,int mid){
u.qa=l.qa||(l.qw&&op[mid].qw&&op[mid].as&&r.qa&&l.as);
u.ws=r.ws||(r.qw&&op[mid].qw&&op[mid].as&&l.ws&&r.as);
u.qw=(l.qw&&op[mid].qw&&r.qw)||(l.qs&&op[mid].as&&r.aw);
u.as=(l.as&&op[mid].as&&r.as)||(l.aw&&op[mid].qw&&r.qs);
u.qs=(l.qs&&op[mid].as&&r.as)||(l.qw&&op[mid].qw&&r.qs);
u.aw=(l.aw&&op[mid].qw&&r.qw)||(l.as&&op[mid].as&&r.aw);
return;
}
void modify(node*&x=root,int L=,int R=n){
if(L==R){
x->a.qa=x->a.ws=x->a.qs=x->a.aw=op[pos].qa;x->a.qw=x->a.as=true;return;
}int M=L+R>>;
if(pos<=M)modify(lson);else modify(rson);
if(x->ch[]&&x->ch[])merge(x->a,x->ch[]->a,x->ch[]->a,M);
else if(x->ch[])x->a=x->ch[]->a;
else if(x->ch[])x->a=x->ch[]->a;
else x->a.init();return;
}
void change(bool f){
if(r1>r2) swap(r1,r2),swap(c1,c2);int dir;
for(int i=;i<;i++)if(c1+dx[i]==c2&&r1+dy[i]==r2)dir=i;
if(dir==) (r2?op[c2].as:op[c2].qw)=f,pos=c2,modify();
else if(dir==) op[c2].qa=f,pos=c2,modify();
else (r1?op[c1].as:op[c1].qw)=f,pos=c1,modify();return;
}
info query(node*x=root,int L=,int R=n){
if(ql<=L&&R<=qr)return x->a;int M=L+R>>;
if(qr<=M)return query(lson);
if(ql>M)return query(rson);
info a=query(lson),b=query(rson),ans;
merge(ans,a,b,M);return ans;
}
void getans(){
if(c1>c2) swap(c1,c2),swap(r1,r2);info pa,pb,pc;
ql=;qr=c1;pa=query();
ql=c1;qr=c2;pb=query();
ql=c2;qr=n;pc=query();
if(r1==r2){
if(r1==){
if(pb.qw||(pa.ws&&pb.aw)||(pb.qs&&pc.qa)||(pa.ws&&pb.as&&pc.qa)) puts("Y");
else puts("N");
}
else{
if(pb.as||(pa.ws&&pb.qs)||(pb.aw&&pc.qa)||(pa.ws&&pb.qw&&pc.qa)) puts("Y");
else puts("N");
}
}
else{
if(r1==){
if(pb.qs||(pa.ws&&pb.as)||(pc.qa&&pb.qw)) puts("Y");
else puts("N");
}
else{
if(pb.aw||(pa.ws&&pb.qw)||(pc.qa&&pb.as)) puts("Y");
else puts("N");
}
}return;
}
inline int read(){
int x=,sig=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')sig=-;ch=getchar();}
while(isdigit(ch))x=*x+ch-'',ch=getchar();
return x*=sig;
}
inline void write(int x){
if(x==){putchar('');return;}if(x<)putchar('-'),x=-x;
int len=,buf[];while(x)buf[len++]=x%,x/=;
for(int i=len-;i>=;i--)putchar(buf[i]+'');return;
}
void init(){
n=read();build();
return;
}
void work(){
while(){
scanf("%s",s);
if(s[]=='E') break;
r1=read();c1=read();r2=read();c2=read();r1--;r2--;
if(s[]=='O') change();
else if(s[]=='C') change();
else getans();
}
return;
}
void print(){
return;
}
int main(){init();work();print();return ;}
上一篇:linux下使用yum安装Apache+php+Mysql+phpMyAdmin


下一篇:view xml 中的 button 调用web客户端事件