题目描述
有一天，由于某种穿越现象作用，你来到了传说中的小人国。小人国的布局非常奇特，整个国家的交通系统可以被看成是一个22行CC列的矩形网格，网格上的每个点代表一个城市，相邻的城市之间有一条道路，所以总共有2C个城市和3C−2条道路。
小人国的交通状况非常槽糕。有的时候由于交通堵塞，两座城市之间的道路会变得不连通，直到拥堵解决，道路才会恢复畅通。初来咋到的你决心毛遂自荐到交通部某份差事，部长听说你来自一个科技高度发达的世界，喜出望外地要求你编写一个查询应答系统，以挽救已经病入膏肓的小人国交通系统。 小人国的交通部将提供一些交通信息给你，你的任务是根据当前的交通情况回答查询的问题。交通信息可以分为以下几种格式：
-
Close r1 c1 r2 c2：相邻的两座城市\((r_1, c_1)(r1,c1)\)和\((r_2, c_2)(r2,c2)\)之间的道路被堵塞了； -
Open r1 c1 r2 c2：相邻的两座城市\((r_1, c_1)(r1,c1)\)和\((r_2, c_2)(r2,c2)\)之间的道路被疏通了； -
Ask r1 c1 r2 c2：询问城市\((r_1, c_1)(r1,c1)\)和\((r_2, c_2)(r2,c2)\)是否连通。如果存在一条路径使得这两条城市连通，则返回Y，否则返回N。
注：\(r_i\)表示行数，\(c_i\)表示列数，\(1 \leq r_i \leq 2\), \(1 \leq c_i \leq C\)。
输入输出格式
输入格式：
第一行只有一个整数CC，表示网格的列数。接下来若干行，每行为一条交通信息，以单独的一行Exit作为结束。我们假设在一开始所有的道路都是堵塞的。我们保证CC小于等于100000100000，信息条数小于等于100000100000.
输出格式：
对于每个查询，输出一个Y或N。
输入输出样例
输入样例#1：
2
Open 1 1 1 2
Open 1 2 2 2
Ask 1 1 2 2
Ask 2 1 2 2
Exit
输出样例#1：
Y
N
说明
数据范围：
对于\(100\%\)的数据，\(1 \leq C \leq 100000\)，$1 \leq \(信息条数\)\leq 100000$。
题解
使用线段树维护。
考虑节点信息的合并，
对于每个点，图大概长这样
\[a_1\qquad a_2\\
-\\
a_3\qquad a_4
\]
-\\
a_3\qquad a_4
\]
其中1-4为四个端点，然后记录6个信息 ： \(a _{1,2},a_{1,3},a_{1,4},a_{3,2},a_{3,4},a_{2,4}\)
其中\(a_{i,j}\)代表i，j两点联不联通，\(a_{i,j} \in \{0,1\}\)。
然后合并：
\[a_1\qquad a_2\qquad b_1\qquad b_2\\
-\\
a_3\qquad a_4 \qquad b_3 \qquad b_4
\]
-\\
a_3\qquad a_4 \qquad b_3 \qquad b_4
\]
然后类似的讨论下，具体可以看代码的update部分。
然后询问\((l,r)\)，先处理出\((1,l-1),(l,r),(r+1,n)\)三段的联通情况，然后讨论。
\[a_1\qquad a_2\qquad b_1\qquad b_2\qquad c_1\qquad c_2\\
-\\
a_3\qquad a_4 \qquad b_3 \qquad b_4 \qquad c_3 \qquad c_4
\]
-\\
a_3\qquad a_4 \qquad b_3 \qquad b_4 \qquad c_3 \qquad c_4
\]
注意一些情况，比如询问\(b_1\)到\(b_4\),可能存在一条路线
\[b_1\rightarrow a_2\rightarrow a_4\rightarrow b_3 \rightarrow b_2
\rightarrow c_1 \rightarrow c_3 \rightarrow b_4\\
\text {或者} b_1\rightarrow a_2\rightarrow a_4\rightarrow b_3 \rightarrow b_4\text{等}
\]
\rightarrow c_1 \rightarrow c_3 \rightarrow b_4\\
\text {或者} b_1\rightarrow a_2\rightarrow a_4\rightarrow b_3 \rightarrow b_4\text{等}
\]
其余几种也类似。
具体细节还是挺多的，不懂看看代码吧。
#include<bits/stdc++.h>
using namespace std;
#define maxn 500050
void read(int &x) {
x=0;int f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
void print(int x) {
if(!x) return ;if(x<0) x=-x,putchar('-');
print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);puts("");}
#define ls p<<1
#define rs p<<1|1
#define mid ((l+r)>>1)
int e[maxn][4],n;
struct segment_tree {
struct node {
int a12,a13,a14,a32,a24,a34;
node() {a12=a13=a14=a32=a24=a34=0;}
}tr[maxn<<2];
node merge(int pos,node x,node y) {
node a;
if(e[pos][1]) {
a.a14|=x.a12&y.a14;
a.a12|=x.a12&y.a12;
a.a32|=x.a32&y.a12;
a.a34|=x.a32&y.a14;
}
if(e[pos][2]) {
a.a34|=x.a34&y.a34;
a.a12|=x.a14&y.a32;
a.a14|=x.a14&y.a34;
a.a32|=x.a34&y.a32;
}
a.a13=x.a13|(x.a12&e[pos][1]&e[pos][2]&y.a13&x.a34);
a.a24=y.a24|(e[pos][1]&e[pos][2]&y.a12&y.a34&x.a24);
return a;
}
void build(int p,int l,int r) {
if(l==r) return tr[p].a12=tr[p].a34=1,void();
build(ls,l,mid),build(rs,mid+1,r);
tr[p]=merge(mid,tr[ls],tr[rs]);
}
void modify(int p,int l,int r,int x,int y) {
if(l==r) {
if(y==1) tr[p].a13=tr[p].a24=tr[p].a14=tr[p].a32=1;
else if(y==2) tr[p].a13=tr[p].a24=tr[p].a14=tr[p].a32=0;
return ;
}
if(x<=mid) modify(ls,l,mid,x,y);
else modify(rs,mid+1,r,x,y);
tr[p]=merge(mid,tr[ls],tr[rs]);
}
node query(int p,int l,int r,int x,int y) {
if(x<=l&&r<=y) return tr[p];
if(x<=mid&&y<=mid) return query(ls,l,mid,x,y);
if(x>mid&&y>mid) return query(rs,mid+1,r,x,y);
return merge(mid,query(ls,l,mid,x,y),query(rs,mid+1,r,x,y));
}
/*
1 2 1 2 1 2
3 4 3 4 3 4
*/
int query(int x,int y,int xx,int yy) {
if(y>yy) swap(x,xx),swap(y,yy);int ans=0;
int b1=e[y-1][1],b2=e[y-1][2],b3=e[yy][1],b4=e[yy][2];
node a1,a2=query(1,1,n,y,yy),a3;//print(a2);
if(y>1) a1=query(1,1,n,1,y-1);
if(yy<n) a3=query(1,1,n,yy+1,n);
if(x==1&&xx==1)
ans=a2.a12|(b1&b2&a1.a24&a2.a32)|(b3&b4&a2.a14&a3.a13)|(b1&b2&b3&b4&a1.a24&a2.a34&a3.a13);
if(x==1&&xx==2)
ans=a2.a14|(b1&b2&a1.a24&a2.a34)|(b3&b4&a2.a12&a3.a13)|(b1&b2&b3&b4&a1.a24&a2.a32&a3.a13);
if(x==2&&xx==1)
ans=a2.a32|(b1&b2&a1.a24&a2.a12)|(b3&b4&a2.a34&a3.a13)|(b1&b2&b3&b4&a1.a24&a2.a14&a3.a13);
if(x==2&&xx==2)
ans=a2.a34|(b1&b2&a1.a24&a2.a14)|(b3&b4&a2.a32&a3.a13)|(b1&b2&b3&b4&a1.a24&a2.a12&a3.a13);
return ans;
}
void print(node i) {printf("%d %d %d %d %d %d\n",i.a12,i.a13,i.a14,i.a32,i.a24,i.a34);}
void debug() {
for(int i=1;i<=3;i++) print(tr[i]);
}
}T;
int main() {
read(n);int a,b,c,d;char s[10];
T.build(1,1,n);
while(1) {
scanf("%s",s+1);if(s[1]=='E') return 0;
read(a),read(b),read(c),read(d);
if(s[1]=='A') {puts(T.query(a,b,c,d)?"Y":"N");continue;}
if(b>d) swap(a,c),swap(b,d);
if(b==d)
if(s[1]=='O') T.modify(1,1,n,b,1);
else T.modify(1,1,n,b,2);
else {
if(s[1]=='O') e[b][a]=1;
else e[b][a]=0;
T.modify(1,1,n,b,3);
}//T.debug();
}
return 0;
}