神仙给我推荐的神仙题
算是CodeForces413E Maze 2D的加强版吧
线段树(6)个值维护联通性
一个矩形(4)个顶点，维护每对顶点的联通性（边和点随便编个号）
(floyd)更新，讨论合并答案（画个图，其实很简单）
然后查询时还有(4)种情况
比如查询(a)的上端到(b)的上端
第一种：(a)上端->(b)上端
第二种：(a)上端->(a)下端->(b)上端
第三种：(a)上端->(b)下端->(b)上端
第四种：(a)上端->(a)下端->>(b)下端->(b)上端
在线段树中分别查询(1)到(a),(a)到(b),(b)到(n)的信息然后判断
注意查询的时候右端点应该减一
实际上查询的是从(a)的上端入口到(b-1)上端出口（也是(b)的上端入口）
因此还要特判(a=b)（可以根据连边情况直接判断）
不知道调试了多久
#include<bits/stdc++.h>
using namespace std;
#define gc c=getchar()
#define r(x) read(x)
#define ls (rt<<1)
#define rs (rt<<1|1)
template<typename T>
inline void read(T&x){
x=0;T k=1;char gc;
while(!isdigit(c)){if(c=='-')k=-1;gc;}
while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}
const int N=100000;
bool E[N][3];
struct seg{
bool f[6];
inline const bool& operator [](const int &x)const{
return f[x];
}
inline bool& operator [](const int &x){
return f[x];
}
inline void init(int x){
static bool g[4][4];
memset(g,0,sizeof(g));
if(E[x][0])g[0][1]=g[1][0]=1;
if(E[x][1])g[0][2]=g[2][0]=1;
if(E[x][2])g[1][3]=g[3][1]=1;
if(E[x+1][0])g[2][3]=g[3][2]=1;
for(int k=0;k<4;++k){
for(int i=0;i<4;++i){
for(int j=0;j<4;++j){
g[i][j]|=g[i][k]&&g[k][j];
}
}
}
f[0]=g[0][1];
f[1]=g[0][2];
f[2]=g[1][3];
f[3]=g[2][3];
f[4]=g[0][3];
f[5]=g[1][2];
}
inline friend seg operator + (const seg &a,const seg &b){
seg ret;
ret[0]=a[0]||(a[1]&&b[0]&&a[2]);
ret[1]=(a[1]&&b[1])||(a[4]&&b[5]);
ret[2]=(a[2]&&b[2])||(a[5]&&b[4]);
ret[3]=b[3]||(b[1]&&a[3]&&b[2]);
ret[4]=(a[4]&&b[2])||(a[1]&&b[4]);
ret[5]=(a[5]&&b[1])||(a[2]&&b[5]);
return ret;
}
}tr[N<<2];
void modify(int rt,int l,int r,int x){
if(l==r){
tr[rt].init(l);
return;
}
int mid=(l+r)>>1;
if(x<=mid)modify(ls,l,mid,x);
else modify(rs,mid+1,r,x);
tr[rt]=tr[ls]+tr[rs];
}
seg query(int rt,int l,int r,int x,int y){
if(x<=l&&r<=y)return tr[rt];
int mid=(l+r)>>1;
if(y<=mid)return query(ls,l,mid,x,y);
else if(x>mid)return query(rs,mid+1,r,x,y);
else return query(ls,l,mid,x,y)+query(rs,mid+1,r,x,y);
}
inline int get(bool x,bool y){
if(x==0&&y==0)return 1;
if(x==0&&y==1)return 4;
if(x==1&&y==0)return 5;
if(x==1&&y==1)return 2;
}
int n;
char s[10];
seg Tmp[2];
inline seg Query(int a,int b){
return (a<b)?query(1,1,n,a,b-1):Tmp[E[a][0]];
}
int main(){
r(n);
Tmp[0][1]=Tmp[0][2]=1;
memset(Tmp[1].f,1,sizeof(Tmp[1].f));
while(1){
scanf("%s",s);
if(s[0]=='E')break;
int a,b,c,d;r(a),r(b),r(c),r(d);--a,--c;
if(b>d)swap(a,c),swap(b,d);
if(s[0]=='A'){
seg l=Query(1,b),m=Query(b,d),r=Query(d,n);
puts((m[get(a,c)]||((l[3]||m[0])&&m[get(a^1,c)])||((r[0]||m[3])&&m[get(a,c^1)])||((l[3]||m[0])&&(r[0]||m[3])&&m[get(a^1,c^1)]))?"Y":"N");
}
else {
if(b==d)E[b][0]=(s[0]=='O');
else E[b][a+1]=(s[0]=='O');
if(b==d&&b>1)modify(1,1,n,b-1);
modify(1,1,n,b);
}
}
}