??有一个 \(2 \times n\) 的初始为空的网格图，要求支持 \(m\) 次操作，每次操作可以加入或删除一条网格的边或者询问两点之间是否联通。
??将每一个方格及其左，上，下三条边作为一个单元，用线段树维护连续一段单元的左上，左下，右上，右下四个顶点互相之间的连通性。父节点四个顶点之间的连通性可以通过左右孩子四个顶点之间的连通性经过运算得到。由于记录四个顶点之间的连通性只需要 \(6\) 个布尔变量，因此一段单元顶点连通状态至多有 \(2^6=64\) 种，可以预处理出所有情况下父节点的顶点连通状态。
??在执行加入或删除操作时，只需要将对应叶节点上的边删除，并更新其到根节点路径上的所有节点状态。在询问时，不妨令询问的两点横坐标是 \(l,r\)，它们会把图分割成三部分：\([1,l],[l,r],[r,n]\)。可以通过线段树求出每个部分的顶点连通状态，而由于询问的两点一定落在 \([l,r]\) 的四个顶点上，可以很轻松地通过 \([1,l],[l,r],[r,n]\) 三部分的联连通状态判断询问节点是否连通。
代码
#include<iostream>
#include<cstdio>
using namespace std;
const int inf=1e9;
const int maxn=1e5+5,maxm=3e5+5;
inline int ls(int u){ return u<<1; }
inline int rs(int u){ return u<<1|1; }
int l[maxm],r[maxm],v[maxm];
int fa[6];
int ff(int u){ return (fa[u]==u)?u:(fa[u]=ff(fa[u])); }
bool flg=true;
inline int calc(int x,int y){
int i,j,z=0;
for (i=0;i<6;i++) fa[i]=i;
for (i=3;i>=0;i--) for (j=3;j>i;j--){
if (x&1) fa[ff(j)]=ff(i); x>>=1;
}
for (i=5;i>=2;i--) for (j=5;j>i;j--){
if (y&1) fa[ff(j)]=ff(i); y>>=1;
}
for (i=0;i<4;i++) for (j=i+1;j<4;j++){
z<<=1; z|=(ff(i<2?i:i+2)==ff(j<2?j:j+2));
}
flg=false;
return z;
}
int mul[1<<6][1<<6];
inline int add(int x,int y){
switch (y){
case 0: return x|0b100000;
case 1: return x|0b010000;
case 2: return x|0b000010;
}
return -1;
}
inline int del(int x,int y){
switch (y){
case 0: return x&0b011111;
case 1: return x&0b101111;
case 2: return x&0b111101;
}
return -1;
}
void build(int u,int _l,int _r){
l[u]=_l; r[u]=_r; v[u]=0;
if (l[u]==r[u]) return;
int _m=(_l+_r)/2;
build(ls(u),_l,_m);
build(rs(u),_m+1,_r);
}
void addedge(int u,int x,int p){
if (l[u]>x||r[u]<x) return;
if (l[u]==r[u]){
v[u]=add(v[u],p); return;
}
addedge(ls(u),x,p);
addedge(rs(u),x,p);
v[u]=mul[v[ls(u)]][v[rs(u)]];
}
void deledge(int u,int x,int p){
if (l[u]>x||r[u]<x) return;
if (l[u]==r[u]){
v[u]=del(v[u],p); return;
}
deledge(ls(u),x,p);
deledge(rs(u),x,p);
v[u]=mul[v[ls(u)]][v[rs(u)]];
}
int query(int u,int _l,int _r){
if (l[u]>_r||r[u]<_l) return 0b010010;
if (l[u]>=_l&&r[u]<=_r) return v[u];
return mul[query(ls(u),_l,_r)][query(rs(u),_l,_r)];
}
char s[10];
int adjust(int &x1,int &y1,int &x2,int &y2){
if (x1>x2){ swap(x1,x2); swap(y1,y2); }
if (y1>y2){ swap(x1,x2); swap(y1,y2); }
if (x1==2) return 2;
if (x2==1) return 1;
return 0;
}
int main(){
int i,j,n;
int x1,y1,x2,y2,t;
int a,b,c;
bool flg;
for (i=0;i<(1<<6);i++) for (j=0;j<(1<<6);j++)
mul[i][j]=calc(i,j);
scanf("%d",&n);
build(1,0,n+2);
flg=true;
while (flg){
scanf("%s",s);
switch (s[0]){
case 'O':
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
t=adjust(x1,y1,x2,y2);
addedge(1,y1,t);
break;
case 'C':
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
t=adjust(x1,y1,x2,y2);
deledge(1,y1,t);
break;
case 'A':
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
adjust(x1,y1,x2,y2);
a=query(1,0,y1-1);
b=query(1,y1,y2-1);
c=query(1,y2,n+2);
if (a&0b000001) b=mul[0b111111][b];
if (c&0b100000) b=mul[b][0b111111];
a=x1-1; c=x2+1;
if (a>c) swap(a,c);
if (a==c) puts("Y");
else switch (a*10+c){
case 01: puts((b&0b100000)?"Y":"N"); break;
case 02: puts((b&0b010000)?"Y":"N"); break;
case 03: puts((b&0b001000)?"Y":"N"); break;
case 12: puts((b&0b000100)?"Y":"N"); break;
case 13: puts((b&0b000010)?"Y":"N"); break;
case 23: puts((b&0b000001)?"Y":"N"); break;
}
break;
case 'E':
flg=false; break;
}
}
return 0;
}原文：https://www.cnblogs.com/Kilo-5723/p/12220493.html