BZOJ 1018 [SHOI2008]堵塞的交通traffic

2022-09-18 09:34:09

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

码农公寓