题意
题目描述
有一天，由于某种穿越现象作用，你来到了传说中的小人国。小人国的布局非常奇特，整个国家的交通系统可以被看成是一个\(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 \text{信息条数}\leq 100000\)。
思路
什么**线段树。 --Mercury
用线段树来写，每个结点维护区间\([l,r]\)的连通性。维护时记录六个值：
- \(ldrd(left-down\ to\ right-down)\)
- \(luru(left-up\ to\ right-up)\)
- \(luld(left-up\ to\ left-down)\)
- \(rurd(right-up\ to\ right-down)\)
- \(lurd(left-up\ to\ right-down)\)
- \(ldru(left-down\ to\ right-up)\)
合并过程其实就是大力模拟的过程，考虑所有的路的经过情况。详见代码的两个update函数。
修改的时候要分类讨论，横线的变化与竖线的变化是不同的情况。
查询的时候要注意，两点可能绕外面的路互相到达，所以还是要大力模拟，考虑绕路和不绕路的情况。
代码的变量名还是比较清楚的，所以就详见代码吧 （才不是我懒得写） 。
AC代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
int n;
int ru[MAXN],rd[MAXN];
struct SegmentTree
{
int l,r;
bool ldrd,luru,luld,rurd,lurd,ldru;
#define l(x) tree[x].l
#define r(x) tree[x].r
#define ldrd(x) tree[x].ldrd
#define luru(x) tree[x].luru
#define luld(x) tree[x].luld
#define rurd(x) tree[x].rurd
#define lurd(x) tree[x].lurd
#define ldru(x) tree[x].ldru
}tree[MAXN<<2];
int read()
{
int re=0;char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) re=(re<<3)+(re<<1)+ch-'0',ch=getchar();
return re;
}
char readc()
{
char ch=getchar();
while(!isalpha(ch)) ch=getchar();
return ch;
}
void update(int p)
{
l(p)=l(p<<1),r(p)=r(p<<1|1);
ldrd(p)=(ldrd(p<<1)&&rd[r(p<<1)]&&ldrd(p<<1|1))||(ldru(p<<1)&&ru[r(p<<1)]&&lurd(p<<1|1));
luru(p)=(luru(p<<1)&&ru[r(p<<1)]&&luru(p<<1|1))||(lurd(p<<1)&&rd[r(p<<1)]&&ldru(p<<1|1));
luld(p)=luld(p<<1)||(luru(p<<1)&&ru[r(p<<1)]&&luld(p<<1|1)&&rd[r(p<<1)]&&ldrd(p<<1));
rurd(p)=rurd(p<<1|1)||(luru(p<<1|1)&&ru[r(p<<1)]&&rurd(p<<1)&&rd[r(p<<1)]&&ldrd(p<<1|1));
lurd(p)=(luru(p<<1)&&ru[r(p<<1)]&&lurd(p<<1|1))||(lurd(p<<1)&&rd[r(p<<1)]&&ldrd(p<<1|1));
ldru(p)=(ldrd(p<<1)&&rd[r(p<<1)]&&ldru(p<<1|1))||(ldru(p<<1)&&ru[r(p<<1)]&&luru(p<<1|1));
}
void update(SegmentTree &re,SegmentTree x,SegmentTree y)
{
re.l=x.l,re.r=y.r;
re.ldrd=(x.ldrd&&rd[x.r]&&y.ldrd)||(x.ldru&&ru[x.r]&&y.lurd);
re.luru=(x.luru&&ru[x.r]&&y.luru)||(x.lurd&&rd[x.r]&&y.ldru);
re.luld=x.luld||(x.luru&&ru[x.r]&&y.luld&&rd[x.r]&&x.ldrd);
re.rurd=y.rurd||(y.luru&&ru[x.r]&&x.rurd&&rd[x.r]&&y.ldrd);
re.lurd=(x.luru&&ru[x.r]&&y.lurd)||(x.lurd&&rd[x.r]&&y.ldrd);
re.ldru=(x.ldrd&&rd[x.r]&&y.ldru)||(x.ldru&&ru[x.r]&&y.luru);
}
void build(int p,int ll,int rr)
{
if(ll==rr)
{
l(p)=ll,r(p)=rr;
luru(p)=ldrd(p)=true;
return ;
}
int mid=(ll+rr)>>1;
build(p<<1,ll,mid);
build(p<<1|1,mid+1,rr);
update(p);
}
void change1(int p,int des,bool up,bool val)
{
int mid=(l(p)+r(p))>>1;
if(mid==des)
{
if(up) ru[des]=val;
else rd[des]=val;
update(p);
return ;
}
if(des<=mid) change1(p<<1,des,up,val);
else change1(p<<1|1,des,up,val);
update(p);
}
void change2(int p,int des,bool val)
{
if(l(p)==r(p))
{
luld(p)=rurd(p)=lurd(p)=ldru(p)=val;
return ;
}
int mid=(l(p)+r(p))>>1;
if(des<=mid) change2(p<<1,des,val);
else change2(p<<1|1,des,val);
update(p);
}
SegmentTree ask(int p,int ll,int rr)
{
if(ll<=l(p)&&r(p)<=rr) return tree[p];
int mid=(l(p)+r(p))>>1;
if(rr<=mid) return ask(p<<1,ll,rr);
else if(ll>mid) return ask(p<<1|1,ll,rr);
else
{
SegmentTree re;
update(re,ask(p<<1,ll,rr),ask(p<<1|1,ll,rr));
return re;
}
}
int main()
{
n=read();
build(1,1,n);
while(true)
{
char opt=readc();
if(opt=='E') break;
int x=read(),y=read(),xx=read(),yy=read();
if(y>yy) swap(x,xx),swap(y,yy);
if(opt=='C')
{
if(y==yy) change2(1,y,false);
else change1(1,y,x==1,false);
}
else if(opt=='O')
{
if(y==yy) change2(1,y,true);
else change1(1,y,x==1,true);
}
else if(opt=='A')
{
SegmentTree ll=ask(1,1,y),mid=ask(1,y,yy),rr=ask(1,yy,n);
if(x==1&&xx==1)
{
if(mid.luru||(ll.rurd&&mid.ldru)||(mid.lurd&&rr.luld)||(ll.rurd&&mid.ldrd&&rr.luld)) puts("Y");
else puts("N");
}
else if(x==2&&xx==2)
{
if(mid.ldrd||(ll.rurd&&mid.lurd)||(mid.ldru&&rr.luld)||(ll.rurd&&mid.luru&&rr.luld)) puts("Y");
else puts("N");
}
else if(x==1&&xx==2)
{
if(mid.lurd||(ll.rurd&&mid.ldrd)||(mid.luru&&rr.luld)||(ll.rurd&&mid.ldru&&rr.luld)) puts("Y");
else puts("N");
}
else if(x==2&&xx==1)
{
if(mid.ldru||(ll.rurd&&mid.luru)||(mid.ldrd&&rr.luld)||(ll.rurd&&mid.lurd&&rr.luld)) puts("Y");
else puts("N");
}
}
}
return 0;
}