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]的，感觉自己好机智呀！

代码们：

 #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 ;}