用8个bool维护即可分别为LURU,LURD,LDRU,LDRD,LULD,RURD,Side[1],Side[2]即可。
Side表示这一块有没有接到右边。Merge一下就可以了。码农题，WA了一次，发现未初始化，就AC了。。
#include <cstdio>
inline int Min(int x,int y) {return x>y?y:x;}
inline void Swap(int &x,int &y) {int t=x;x=y;y=t;}
inline void Get_Int(int &x)
{
char ch=getchar(); x=;
while (ch<'' || ch>'') ch=getchar();
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
}
//========================================
const int Maxn=;
struct Node
{
bool LURU,LURD,LDRU,LDRD,LULD,RURD,Side[];
}Tree[Maxn<<],Null;
int x1,y1,x2,y2,n;
char ch[];
inline Node Merge(Node L,Node R)
{
Node Ret; Ret=Null;
Ret.Side[]=R.Side[],Ret.Side[]=R.Side[];
if ((L.LURU&&R.LURU&&L.Side[]) || (L.LURD&&R.LDRU&&L.Side[])) Ret.LURU=true;
if ((L.LDRD&&R.LDRD&&L.Side[]) || (L.LDRU&&R.LURD&&L.Side[])) Ret.LDRD=true;
if ((L.LURU&&R.LURD&&L.Side[]) || (L.LURD&&R.LDRD&&L.Side[])) Ret.LURD=true;
if ((L.LDRD&&R.LDRU&&L.Side[]) || (L.LDRU&&R.LURU&&L.Side[])) Ret.LDRU=true;
if (L.LULD || (L.LURU&&L.LDRD&&R.LULD&&L.Side[]&&L.Side[])) Ret.LULD=true;
if (R.RURD || (R.LURU&&R.LDRD&&L.RURD&&L.Side[]&&L.Side[])) Ret.RURD=true;
return Ret;
}
void Build(int o,int l,int r)
{ if (l==r)
{
Tree[o].LURU=Tree[o].LDRD=true;
return;
}
int mid=(l+r)>>;
Build(o<<,l,mid),Build(o<<|,mid+,r);
Tree[o]=Merge(Tree[o<<],Tree[o<<|]);
}
void Modify_X(int o,int l,int r,int pos,bool kind)
{
if (l==r)
{
Tree[o].LULD=Tree[o].RURD=Tree[o].LURD=Tree[o].LDRU=kind;
return;
}
int mid=(l+r)>>;
if (pos<=mid) Modify_X(o<<,l,mid,pos,kind); else Modify_X(o<<|,mid+,r,pos,kind);
Tree[o]=Merge(Tree[o<<],Tree[o<<|]);
}
void Modify_Y(int o,int l,int r,int pos,int x,bool kind)
{
if (l==r)
{
Tree[o].Side[x]=kind;
return;
}
int mid=(l+r)>>;
if (pos<=mid) Modify_Y(o<<,l,mid,pos,x,kind); else Modify_Y(o<<|,mid+,r,pos,x,kind);
Tree[o]=Merge(Tree[o<<],Tree[o<<|]);
}
inline void Close()
{
if (x1==x2) Modify_Y(,,n,Min(y1,y2),x1,false);
if (y1==y2) Modify_X(,,n,y1,false);
}
inline void Open()
{
if (x1==x2) Modify_Y(,,n,Min(y1,y2),x1,true);
if (y1==y2) Modify_X(,,n,y1,true);
}
Node Query(int o,int l,int r,int p,int q)
{
if (l==p && r==q)
{
Node Ret=Tree[o];
return Ret;
}
int mid=(l+r)>>;
if (q<=mid) return Query(o<<,l,mid,p,q);
if (p>=mid+) return Query(o<<|,mid+,r,p,q);
if (p<=mid && q>=mid+)
return Merge(Query(o<<,l,mid,p,mid),Query(o<<|,mid+,r,mid+,q));
}
inline bool Check()
{
if (y1>y2) Swap(y1,y2),Swap(x1,x2);
Node Pre,Suf,Now;
if (y1->=) Pre=Query(,,n,,y1-); else Pre=Null;
if (y2+<=n) Suf=Query(,,n,y2+,n); else Suf=Null;
Now=Query(,,n,y1,y2);
if (x1==x2)
{
if ((x1==) && ((Now.LURU) || (Pre.RURD&&Pre.Side[]&&Pre.Side[]&&Now.LDRU) || (Suf.LULD&&Now.Side[]&&Now.Side[]&&Now.LURD) || (Pre.RURD&&Suf.LULD&&Now.Side[]&&Now.Side[]&&Pre.Side[]&&Pre.Side[]&&Now.LDRD))) return true;
if ((x1==) && ((Now.LDRD) || (Pre.RURD&&Pre.Side[]&&Pre.Side[]&&Now.LURD) || (Suf.LULD&&Now.Side[]&&Now.Side[]&&Now.LDRU) || (Pre.RURD&&Suf.LULD&&Now.Side[]&&Now.Side[]&&Pre.Side[]&&Pre.Side[]&&Now.LURU))) return true;
} else
{
if ((x1== && x2==) && ((Now.LURD) || (Pre.RURD&&Pre.Side[]&&Pre.Side[]&&Now.LDRD) || (Suf.LULD&&Now.Side[]&&Now.Side[]&&Now.LURU) || (Pre.RURD&&Suf.LULD&&Now.Side[]&&Now.Side[]&&Pre.Side[]&&Pre.Side[]&&Now.LDRU))) return true;
if ((x1== && x2==) && ((Now.LDRU) || (Pre.RURD&&Pre.Side[]&&Pre.Side[]&&Now.LURU) || (Suf.LULD&&Now.Side[]&&Now.Side[]&&Now.LDRD) || (Pre.RURD&&Suf.LULD&&Now.Side[]&&Now.Side[]&&Pre.Side[]&&Pre.Side[]&&Now.LURD))) return true;
}
return false;
}
inline void Ask() {if (Check()) puts("Y"); else puts("N");}
int main()
{
// freopen("c.in","r",stdin);
Get_Int(n); Build(,,n);
Null.LURU=Null.LURD=Null.LDRU=Null.LDRD=Null.Side[]=Null.Side[]=Null.LULD=Null.RURD=false;
while (scanf("%s",ch)!=EOF)
{
if (ch[]=='E') break;
Get_Int(x1),Get_Int(y1),Get_Int(x2),Get_Int(y2);
if (ch[]=='O') Open();
if (ch[]=='C') Close();
if (ch[]=='A') Ask();
}
return ;
}
C++