题目
题目描述
有一天，由于某种穿越现象作用，你来到了传说中的小人国。小人国的布局非常奇特，整个国家的交通系统可以被看成是一个$2$行$C$列的矩形网格，网格上的每个点代表一个城市，相邻的城市之间有一条道路，所以总共有$2C$个城市和$3C-2$条道路。
小人国的交通状况非常槽糕。有的时候由于交通堵塞，两座城市之间的道路会变得不连通，直到拥堵解决，道路才会恢复畅通。初来咋到的你决心毛遂自荐到交通部某份差事，部长听说你来自一个科技高度发达的世界，喜出望外地要求你编写一个查询应答系统，以挽救已经病入膏肓的小人国交通系统。 小人国的交通部将提供一些交通信息给你，你的任务是根据当前的交通情况回答查询的问题。交通信息可以分为以下几种格式：
Close r1 c1 r2 c2：相邻的两座城市$(r_1, c_1)$和$(r_2, c_2)$之间的道路被堵塞了；Open r1 c1 r2 c2：相邻的两座城市$(r_1, c_1)$和$(r_2, c_2)$之间的道路被疏通了；Ask r1 c1 r2 c2：询问城市$(r_1, c_1)$和$(r_2, c_2)$是否连通。如果存在一条路径使得这两条城市连通，则返回Y，否则返回N。
注：$r_i$表示行数，$c_i$表示列数，$1 \leq r_i \leq 2, 1 \leq c_i \leq C$。
输入输出格式
输入格式：
第一行只有一个整数$C$，表示网格的列数。接下来若干行，每行为一条交通信息，以单独的一行Exit作为结束。我们假设在一开始所有的道路都是堵塞的。我们保证$C$小于等于$100000$，信息条数小于等于$100000$。
输出格式：
对于每个查询，输出一个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$。
题解
一个点到另一个点只有$3$种情况：
- 先向左走，最后回到右边
- 直接从左走到右
- 先向右走，最后回到左边
线段树每个节点记录最左端点向右走再向左走是否能走到最左边的另一行，最右端点向左走再向右走是否能走到最右边的另一行，最左与最右$4$个端点两两之间的连通性，两个儿子之间相接的部分是否相通
合并的时候分类讨论一下就行了
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define tl (k<<1)
# define tr (k<<1|1)
# define mid (l+r>>1)
using namespace std;
const int MAX=1e5+5;
struct p{
bool _val[2],__val[2];
bool val[2][2];
}s[MAX<<2];
int n;
char A[10];
int read()
{
int x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
p pus(p b,p c,int l,int r,bool *fl)
{
p a;
a._val[0]=(b._val[0]||(c._val[0]&&b.val[0][0]&&b.val[1][1]&&fl[0]&&fl[1])),a._val[1]=(c._val[1]||(b._val[1]&&c.val[0][0]&&c.val[1][1]&&fl[0]&&fl[1]));
a.val[0][0]=(b.val[0][0]&&c.val[0][0]&&fl[0])||(b.val[0][1]&&c.val[1][0]&&fl[1]);
a.val[1][1]=(b.val[1][0]&&c.val[0][1]&&fl[0])||(b.val[1][1]&&c.val[1][1]&&fl[1]);
a.val[1][0]=(b.val[1][0]&&c.val[0][0]&&fl[0])||(b.val[1][1]&&c.val[1][0]&&fl[1]);
a.val[0][1]=(b.val[0][0]&&c.val[0][1]&&fl[0])||(b.val[0][1]&&c.val[1][1]&&fl[1]);
a.__val[0]=fl[0],a.__val[1]=fl[1];
return a;
}
void change(int l,int r,int k,int x,int y,int _x,int _y,bool fl)
{
if(r<y||_y<l) return;
if(y==mid&&x==_x)
{
s[k].__val[x-1]=fl;
return void(s[k]=pus(s[tl],s[tr],l,r,s[k].__val));
}
if(l==r)
{
s[k].val[0][0]=s[k].val[1][1]=1;
return void(s[k]._val[0]=s[k]._val[1]=s[k].val[0][1]=s[k].val[1][0]=(x!=_x&&fl));
}
change(l,mid,tl,x,y,_x,_y,fl),change(mid+1,r,tr,x,y,_x,_y,fl),s[k]=pus(s[tl],s[tr],l,r,s[k].__val);
}
p ask(int l,int r,int k,int L,int R)
{
if(l==L&&r==R) return s[k];
if(R<=mid) return ask(l,mid,tl,L,R);
if(L>mid) return ask(mid+1,r,tr,L,R);
return pus(ask(l,mid,tl,L,mid),ask(mid+1,r,tr,mid+1,R),l,r,s[k].__val);
}
bool ASK(int x,int y,int _x,int _y)
{
p a=ask(1,n,1,1,y),b=ask(1,n,1,y,_y),c=ask(1,n,1,_y,n);
if(b.val[x-1][_x-1]) return 1;
if(a._val[1]&&b.val[x-1^1][_x-1]) return 1;
if(c._val[0]&&b.val[x-1][_x-1^1]) return 1;
if(a._val[1]&&c._val[0]&&b.val[x-1^1][_x-1^1]) return 1;
return 0;
}
void build(int l=1,int r=n,int k=1)
{
if(l==r) return void(s[k].val[0][0]=s[k].val[1][1]=1);
build(l,mid,tl),build(mid+1,r,tr);
}
int main()
{
n=read(),scanf("%s",A),build();
for(int x,y,_x,_y;A[0]!='E';scanf("%s",A))
{
x=read(),y=read(),_x=read(),_y=read();
if(y>_y) swap(y,_y),swap(x,_x);
if(A[0]=='A') puts(ASK(x,y,_x,_y)?"Y":"N");
else change(1,n,1,x,y,_x,_y,A[0]=='O');
}
return 0;
}
