题目：https://www.lydsy.com/JudgeOnline/problem.php?id=1018
巧妙的线段树。维护矩阵四个角的连通性。
考虑两个点连通的可能路径分成3部分：两点左边、两点中间、两点右边；
就拿中间部分来说，需要这个矩阵的四个角的连通性。所以就用线段树维护一下。
注意不要写得冗余了。比如同一块的左上到右下已经考虑过自己的左上到左下+左下到右下，更新别的块的时候不用再讨论第二种情况了。
还要注意不要搞混 r 和 c 。
（结构体真好用……）（u：lu-ru d：ld-rd U：mu D：md p：ld-ru q：lu-rd l：lu-ld r：ru-rd）
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e5+;
int n,tot=,r1,c1,r2,c2;
bool b[N<<][];//1:lu-ru 2:ld-rd 3:lu-rd 4:ld-ru 5:lu-ld 6:ru-rd 7:mu-mu 8:md-md
struct Node{
int ls,rs;
}a[N<<];
struct Lt{bool l,r,u,d,U,D,p,q;}w[N<<];
void build(int l,int r,int cr)
{
if(l==r)
{
// b[cr][1]=1;b[cr][2]=1;
w[cr].u=w[cr].d=w[cr].U=w[cr].D=;
return;
}
int mid=((l+r)>>);
a[cr].ls=++tot;build(l,mid,tot);
a[cr].rs=++tot;build(mid+,r,tot);
}
//void pushup(int cr)
//{
// int ls=a[cr].ls,rs=a[cr].rs;
// if(b[ls][5]||(b[ls][1]&&b[cr][7]&&b[rs][5]&&b[cr][8]&&b[ls][2]))b[cr][5]=1;else b[cr][5]=0;
// if(b[rs][6]||(b[rs][1]&&b[cr][7]&&b[ls][6]&&b[cr][8]&&b[rs][2]))b[cr][6]=1;else b[cr][6]=0;
// if(b[cr][7])
// {
// if((b[ls][1]||(b[ls][5]&&b[ls][4]))&&(b[rs][1]||(b[rs][3]&&b[rs][6])))b[cr][1]=1;else b[cr][1]=0;
// if((b[ls][4]||(b[ls][5]&&b[ls][1]))&&(b[rs][3]||(b[rs][1]&&b[rs][6])))b[cr][2]=1;else b[cr][2]=0;
// if(b[ls][1]&&b[rs][3])b[cr][3]=1;else b[cr][3]=0;
// if(b[ls][4]&&b[rs][1])b[cr][4]=1;else b[cr][4]=0;
// }
// if(b[cr][8])
// {
// if((b[ls][2]||(b[ls][5]&&b[ls][3]))&&(b[rs][2]||(b[rs][4]&&b[rs][6])))b[cr][2]=1;
// if((b[ls][3]||(b[ls][5]&&b[ls][2]))&&(b[rs][4]||(b[rs][2]&&b[rs][4])))b[cr][1]=1;
// if(b[ls][2]&&b[rs][4])b[cr][4]=1;if(b[ls][3]&&b[rs][2])b[cr][3]=1;
// }
//}
void pushup(Lt &k,Lt x,Lt y)// &!!!!!
{
k.l=x.l|(x.u & k.U & y.l & k.D & x.d);
k.r=y.r|(y.u & k.U & x.r & k.D & y.d);
k.u=(x.u & k.U & y.u)|(x.q & k.D & y.p);
k.d=(x.d & k.D & y.d)|(x.p & k.U & y.q);
k.p=(x.d & k.D & y.p)|(x.p & k.U & y.u);
k.q=(x.u & k.U & y.q)|(x.q & k.D & y.d);
}
//void mdfy(int l,int r,int cr,bool p)
//{
// if(l>=r1&&r<=r2)
// {
// if(c1!=c2){b[cr][3]=p;b[cr][4]=p;b[cr][5]=p;b[cr][6]=p;}
// else if(c1==1){
// b[cr][1]=p;b[cr][7]=p;
// if(b[a[cr].ls][5])b[cr][4]=1;if(b[a[cr].rs][5])b[cr][3]=1;
// }
// else {
// b[cr][2]=p;b[cr][8]=p;
// if(b[a[cr].ls][5])b[cr][3]=1;if(b[a[cr].rs][5])b[cr][4]=1;
// }
// return;
// }
// int mid=l+r>>1;
// if(mid>=r2)mdfy(l,mid,a[cr].ls,p);
// else if(mid<r1)mdfy(mid+1,r,a[cr].rs,p);
// else b[cr][c1==1?7:8]=1;
// pushup(cr,a[cr].ls,a[cr].rs);
//}
void mdfyr(int l,int r,int cr,bool f)
{
int mid=((l+r)>>);
if(mid==c1)
{
if(r1==)w[cr].U=f;else w[cr].D=f;
pushup(w[cr],w[a[cr].ls],w[a[cr].rs]);return;//pushup
}
if(c1<mid)mdfyr(l,mid,a[cr].ls,f);
else mdfyr(mid+,r,a[cr].rs,f);
pushup(w[cr],w[a[cr].ls],w[a[cr].rs]);
}
void mdfyc(int l,int r,int cr,bool f)
{
if(l==r)
{
w[cr].l=w[cr].r=w[cr].p=w[cr].q=f;return;
}
int mid=((l+r)>>);
if(mid>=c1)mdfyc(l,mid,a[cr].ls,f);
else mdfyc(mid+,r,a[cr].rs,f);
pushup(w[cr],w[a[cr].ls],w[a[cr].rs]);
}
//bool query(int l,int r,int cr,int r1,int c1,int r2,int c2)
//{
// if(l==r1&&r==r2)
// {
// if(c1==1&&c2==1)return b[cr][1];
// if(c1==1&&c2==2)return b[cr][3];
// if(c1==2&&c2==1)return b[cr][4];
// if(c1==2&&c2==2)return b[cr][2];
// }
// int mid=l+r>>1,ls=a[cr].ls,rs=a[cr].rs;
// if(mid>=r2)return query(l,mid,ls,r1,c1,r2,c2);
// else if(mid<r1)return query(mid+1,r,rs,r1,c1,r2,c2);
// else return ((b[cr][7]&&query(l,mid,ls,r1,c1,mid,1)&&query(mid+1,r,rs,mid,1,r2,c2))
// ||(b[cr][8]&&query(l,mid,ls,r1,c1,mid,2)&&query(mid+1,r,rs,mid,2,r2,c2)));
//}
//bool query(int l,int r,int cr,int r1,int c1,int r2,int c2)
//{
//// printf("l=%d r=%d r1=%d c1=%d r2=%d c2=%d\n",l,r,r1,c1,r2,c2);
// if(l==c1&&r==c2)
// {
// if(r1==r2){if(r1==1)return w[cr].u;else return w[cr].d;}
// else {if(r1==1)return w[cr].q;else return w[cr].p;}
// }
// int mid=l+r>>1,ls=a[cr].ls,rs=a[cr].rs;
// if(mid>=c2)return query(l,mid,ls,r1,c1,r2,c2);
// else if(mid<c1)return query(mid+1,r,rs,r1,c1,r2,c2);
// else return (w[cr].U&query(l,mid,ls,r1,c1,mid,1)&query(mid+1,r,rs,mid+1,1,r2,c2))
// |(w[cr].D&query(l,mid,ls,r1,c1,mid,2)&query(mid+1,r,rs,mid+1,2,r2,c2));
//}
Lt query(int l,int r,int cr,int L,int R)
{
if(l>=L&&r<=R)return w[cr];
int mid=((l+r)>>),ls=a[cr].ls,rs=a[cr].rs;
if(mid>=R)return query(l,mid,ls,L,R);
else if(mid<L)return query(mid+,r,rs,L,R);
else{
Lt ret=w[cr];
pushup(ret,query(l,mid,ls,L,R),query(mid+,r,rs,L,R));
return ret;
}
}
int main()
{
scanf("%d",&n);char ch[];
build(,n,);
while()
{
scanf("%s",ch);if(ch[]=='E')return ;
scanf("%d%d%d%d",&r1,&c1,&r2,&c2);
if(c1>c2)swap(r1,r2),swap(c1,c2);
if(ch[]=='O'||ch[]=='C')
{
if(r1==r2)mdfyr(,n,,ch[]=='O'?:);
else mdfyc(,n,,ch[]=='O'?:);
}
if(ch[]=='A')
{
// if(query(1,n,1,r1,c1,r2,c2))printf("Y\n");else printf("N\n");
bool flag=;
Lt x=query(,n,,,c1),y=query(,n,,c1,c2),z=query(,n,,c2,n);
if(r1==&&r2==)flag=y.u|(x.r & y.d & z.l)|(y.q & z.l)|(x.r & y.p);
if(r2==&&r2==)flag=y.d|(x.r & y.u & z.l)|(x.r & y.q)|(y.p & z.l);
if(r1==&&r2==)flag=y.q|(x.r & y.p & z.l)|(x.r & y.d)|(y.u & z.l);
if(r1==&&r2==)flag=y.p|(x.r & y.q & z.l)|(x.r & y.u)|(y.d & z.l);
if(flag)printf("Y\n");else printf("N\n");
}
}
}