题目

2行c列个点，开始时互不联通，支持给同一列或着同一行相邻的两个点连边，和询问两个点能否在一个联通块里。

1≤C≤100000 1<=操作数<=100000;

题解

线段树的又一个骚操作。

我们把2*2的4个点看作线段树上的叶子结点。其他节点就是其儿子的合并（叶子结点的父亲表示2*4八个点，然后是2*8，2*16）。

然后在节点上维护节点表示的点的联通信息。

                                             

信息维护六种，就是用同种颜色连接的点是否联通。

所以信息合并时要写一堆。

然后发现这样叶子节点的信息不好修改（你写写就知道了），所以我们在叶子结点上额外记录实际连边的情况。

查询大体思路是把所有点分成三分，然后枚举所有情况。（假如两个点在同一列要特判）

 

 

 

 

（这些线代表的是连通情况，并不是实际路线）

 然后就可以通过了

 这个题告诉我：对拍是个好东西

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 using namespace std;  7 const int N=110010;  8 int n;  9 struct jz{ 10     int a[8]; 11 }hhh; 12 struct tree{ 13     int l,r; 14     jz z,tru;  15 }tr[N*8]; 16 void build(int l,int r,int now){ 17     tr[now].l=l;tr[now].r=r; 18     if(l==r){ 19         return; 20     } 21     int mid=(tr[now].l+tr[now].r)>>1; 22     build(l,mid,now*2); 23     build(mid+1,r,now*2+1); 24 } 25 void update(int now){ 26     tr[now].z.a[2]=(tr[now*2].z.a[5]&tr[now*2+1].z.a[6])|(tr[now*2].z.a[2]&tr[now*2+1].z.a[2]); 27     tr[now].z.a[4]=(tr[now*2].z.a[6]&tr[now*2+1].z.a[5])|(tr[now*2].z.a[4]&tr[now*2+1].z.a[4]); 28     tr[now].z.a[5]=(tr[now*2].z.a[2]&tr[now*2+1].z.a[5])|(tr[now*2].z.a[5]&tr[now*2+1].z.a[4]); 29     tr[now].z.a[6]=(tr[now*2].z.a[4]&tr[now*2+1].z.a[6])|(tr[now*2].z.a[6]&tr[now*2+1].z.a[2]); 30     tr[now].z.a[1]=tr[now*2].z.a[1]|(tr[now*2].z.a[2]&tr[now*2].z.a[4]&tr[now*2+1].z.a[1]); 31     tr[now].z.a[3]=tr[now*2+1].z.a[3]|(tr[now*2+1].z.a[2]&tr[now*2+1].z.a[4]&tr[now*2].z.a[3]); 32 } 33 void update(int x,int k,int c,int now){ 34     if(tr[now].l==tr[now].r){ 35         tr[now].tru.a[k]=c; 36         for(int i=1;i<=6;i++){ 37             tr[now].z.a[i]=tr[now].tru.a[i]; 38         } 39         tr[now].z.a[5]=(tr[now].tru.a[2]&tr[now].tru.a[3])|(tr[now].tru.a[1]&tr[now].tru.a[4]); 40         tr[now].z.a[6]=(tr[now].tru.a[4]&tr[now].tru.a[3])|(tr[now].tru.a[1]&tr[now].tru.a[2]); 41         tr[now].z.a[2]=tr[now].z.a[2]|(tr[now].z.a[5]&tr[now].z.a[3])|(tr[now].z.a[6]&tr[now].z.a[1]); 42         tr[now].z.a[4]=tr[now].z.a[4]|(tr[now].z.a[5]&tr[now].z.a[1])|(tr[now].z.a[6]&tr[now].z.a[3]); 43         tr[now].z.a[3]=tr[now].z.a[3]|(tr[now].z.a[5]&tr[now].z.a[2])|(tr[now].z.a[6]&tr[now].z.a[4]); 44         tr[now].z.a[1]=tr[now].z.a[1]|(tr[now].z.a[5]&tr[now].z.a[4])|(tr[now].z.a[6]&tr[now].z.a[2]); 45 //        for(int i=1;i<=6;i++){ 46 //            cout<
           
            <<" "; 47 // } 48 // cout<
            
             >1; 52 if(x<=mid)update(x,k,c,now*2); 53 else update(x,k,c,now*2+1); 54 update(now); 55 } 56 jz hb(jz a,jz b,jz c){ 57 c.a[2]=(a.a[5]&b.a[6])|(a.a[2]&b.a[2]); 58 c.a[4]=(a.a[6]&b.a[5])|(a.a[4]&b.a[4]); 59 c.a[5]=(a.a[2]&b.a[5])|(a.a[5]&b.a[4]); 60 c.a[6]=(a.a[4]&b.a[6])|(a.a[6]&b.a[2]); 61 c.a[1]=a.a[1]|(a.a[2]&a.a[4]&b.a[1]); 62 c.a[3]=b.a[3]|(b.a[2]&b.a[4]&a.a[3]); 63 return c; 64 } 65 jz check(int l,int r,int now){ 66 if(tr[now].l==l&&tr[now].r==r){ 67 return tr[now].z; 68 } 69 int mid=(tr[now].l+tr[now].r)>>1; 70 if(l>mid)return check(l,r,now*2+1); 71 else if(r<=mid)return check(l,r,now*2); 72 else { 73 return hb(check(l,mid,now*2),check(mid+1,r,now*2+1),hhh); 74 } 75 } 76 int main(){ 77 scanf("%d",&n); 78 build(1,n+2,1); 79 string s; 80 while(cin>>s){ 81 if(s[0]=='E')break; 82 int x1,y1,x2,y2; 83 scanf("%d%d%d%d",&x1,&y1,&x2,&y2); 84 if(y1>y2)swap(x2,x1),swap(y1,y2); 85 if(s[0]=='O'){ 86 if(y1==y2){ 87 update(y1,3,1,1); 88 update(y1+1,1,1,1); 89 } 90 else { 91 if(x1==1)update(y1+1,2,1,1); 92 else update(y1+1,4,1,1); 93 } 94 } 95 else if(s[0]=='C'){ 96 if(y1==y2){ 97 update(y1,3,0,1); 98 update(y1+1,1,0,1); 99 }100 else {101 if(x1==1)update(y1+1,2,0,1);102 else update(y1+1,4,0,1);103 }104 }105 else {106 if(y1==y2){107 jz x=check(1,y1,1);108 jz y=check(y1+1,n+1,1);109 if(x.a[3]|y.a[1])printf("Y\n");110 else printf("N\n");111 }112 else{ 113 jz z=check(y1+1,y2,1);114 jz x=check(1,y1,1);115 jz y=check(y2+1,n+1,1);116 if(x1==x2){117 if(x1==1){118 if(z.a[2]|(x.a[3]&z.a[4]&y.a[1])|(x.a[3]&z.a[6])|(z.a[5]&y.a[1]))printf("Y\n");119 else printf("N\n");120 }121 else if(z.a[4]|(x.a[3]&z.a[2]&y.a[1])|(x.a[3]&z.a[5])|(z.a[6]&y.a[1]))printf("Y\n");122 else printf("N\n");123 }124 else{125 if(x1==1){126 if(z.a[5]|(x.a[3]&z.a[4])|(y.a[1]&z.a[2])|(x.a[3]&z.a[6]&y.a[1]))printf("Y\n");127 else printf("N\n");128 }129 else if(z.a[6]|(x.a[3]&z.a[2])|(y.a[1]&z.a[4])|(x.a[3]&z.a[5]&y.a[1]))printf("Y\n");130 else printf("N\n");131 }132 }133 }134 }135 return 0; 136 }