题目描述

有一天，由于某种穿越现象作用，你来到了传说中的小人国。小人国的布局非常奇特，整个国家的交通系统可

以被看成是一个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；

题解

这么**的题我居然能一A。。。

我写的比较麻烦，用二元组[0/1][0/1]来表示当前矩形的四个角，再去维护每个小矩形，线段树维护合并后的大矩形。

讨论比较恶心。。

代码

#include
     
      #include
      
       #include
       
        #define N 100009using namespace std;char s[10];int n;inline int rd(){    int x=0;char c=getchar();bool f=0;    while(!isdigit(c)){
   if(c=='-')f=1;c=getchar();}    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}    return f?-x:x;}struct node{    bool a[2][2][2][2];    node operator +(const node &b)const{        node c;        c.a[0][0][0][1]=(a[0][0][1][1]&&b.a[1][0][0][1])||(a[0][0][0][1]&&b.a[0][0][0][1]);        c.a[0][0][1][0]=(a[0][0][1][0])||(a[0][0][0][1]&&b.a[0][0][1][0]&&a[1][0][1][1]);        c.a[0][0][1][1]=(a[0][0][1][1]&&b.a[1][0][1][1])||(a[0][0][0][1]&&b.a[0][0][1][1]);        c.a[1][0][0][1]=(a[1][0][1][1]&&b.a[1][0][0][1])||(a[1][0][0][1]&&b.a[0][0][0][1]);        c.a[1][0][1][1]=(a[1][0][1][1]&&b.a[1][0][1][1])||(a[1][0][0][1]&&b.a[0][0][1][1]);        c.a[0][1][1][1]=(b.a[0][1][1][1])||(a[0][1][1][1]&&b.a[0][0][0][1]&&b.a[1][0][1][1]);        return c;    }    inline void clear(){memset(a,0,sizeof(a));}    inline void print(){      cout<
        
         <<" "<
         
          <<" "      <
          
           <<" "<
           
            <<" "<
            
             <<" "<
             
              <
              
               >1;tr[cnt].ls=++tot;tr[cnt].rs=++tot; build(tr[cnt].ls,l,mid);build(tr[cnt].rs,mid+1,r);}void upd(int cnt,int l,int r,int tag,int x,int y){ if(l==r){ if(tag<2)now[l].a[tag][0][tag][1]=y; else now[l].a[0][tag-2][1][tag-2]=y; tr[cnt].val.clear(); tr[cnt].val.a[0][0][1][0]=now[l].a[0][0][1][0]||(now[l].a[0][0][0][1]&&now[l].a[0][1][1][1]&&now[l].a[1][0][1][1]); tr[cnt].val.a[0][0][0][1]=now[l].a[0][0][0][1]||(now[l].a[0][0][1][0]&&now[l].a[1][0][1][1]&&now[l].a[0][1][1][1]); tr[cnt].val.a[0][0][1][1]=(now[l].a[0][0][0][1]&&now[l].a[0][1][1][1])||(now[l].a[0][0][1][0]&&now[l].a[1][0][1][1]); tr[cnt].val.a[1][0][0][1]=(now[l].a[0][0][1][0]&&now[l].a[0][0][0][1])||(now[l].a[1][0][1][1]&&now[l].a[0][1][1][1]); tr[cnt].val.a[1][0][1][1]=(now[l].a[1][0][1][1])||(now[l].a[0][0][1][0]&&now[l].a[0][0][0][1]&&now[l].a[0][1][1][1]); tr[cnt].val.a[0][1][1][1]=(now[l].a[0][1][1][1])||(now[l].a[0][0][0][1]&&now[l].a[0][0][1][0]&&now[l].a[1][0][1][1]); // cout<
               
                <<" ";tr[cnt].val.print(); return; } int mid=(l+r)>>1; if(mid>=x)upd(tr[cnt].ls,l,mid,tag,x,y); else upd(tr[cnt].rs,mid+1,r,tag,x,y); tr[cnt].val=tr[tr[cnt].ls].val+tr[tr[cnt].rs].val;}node _query(int cnt,int l,int r,int x,int tag){ if(l==r){ node x; int xx=tr[cnt].val.a[0][tag][1][tag]; x.a[0][0][0][1]=x.a[1][0][1][1]=1; x.a[0][0][1][1]=x.a[0][0][1][0]=x.a[0][1][1][1]=x.a[1][0][0][1]=xx; return x; } int mid=(l+r)>>1; if(mid>=x)return _query(tr[cnt].ls,l,mid,x,tag); else return _query(tr[cnt].rs,mid+1,r,x,tag);}node query(int cnt,int l,int r,int L,int R){ if(L>R)return node(); if(l>=L&&r<=R)return tr[cnt].val; int mid=(l+r)>>1; if(mid>=L&&mid
                
                 =L)return query(tr[cnt].ls,l,mid,L,R); else return query(tr[cnt].rs,mid+1,r,L,R); }int main(){ n=rd(); build(1,1,n-1); int r1,r2,x,y; while(1){ scanf("%s",s);if(s[0]=='E')break; r1=rd();x=rd();r2=rd();y=rd();r1--;r2--; if(x>y)swap(x,y),swap(r1,r2); if(s[0]=='C'){ if(x==y){ if(x!=n)upd(1,1,n-1,2,x,0);if(x>1)upd(1,1,n-1,3,x-1,0);} else upd(1,1,n-1,r1,min(x,y),0); } else if(s[0]=='O'){ if(x==y){ if(x!=n)upd(1,1,n-1,2,x,1);if(x>1)upd(1,1,n-1,3,x-1,1);} else upd(1,1,n-1,r1,min(x,y),1); } else{ bool ans=0; node xx=query(1,1,n-1,x,y-1),x1=query(1,1,n-1,1,x-1),x2=query(1,1,n-1,y,n-1); if(x==y)xx=_query(1,1,n-1,x==1?x:x-1,x==1?0:1); // xx.print();x1.print();x2.print(); if(r1){ if(r2){ if(xx.a[1][0][1][1])ans=1; if(x1.a[0][1][1][1]&&x2.a[0][0][1][0]&&xx.a[0][0][0][1])ans=1; } else{ if(xx.a[1][0][0][1])ans=1; if(x1.a[0][1][1][1]&&xx.a[0][0][0][1])ans=1; if(x2.a[0][0][1][0]&&xx.a[1][0][1][1])ans=1; } } else{ if(r2){ if(xx.a[0][0][1][1])ans=1; if(x1.a[0][1][1][1]&&xx.a[1][0][1][1])ans=1; if(x2.a[0][0][1][0]&&xx.a[0][0][0][1])ans=1; } else{ if(xx.a[0][0][0][1])ans=1; if(x1.a[0][1][1][1]&&x2.a[0][0][1][0]&&xx.a[1][0][1][1])ans=1; } } if(ans)puts("Y");else puts("N"); } } return 0;}