本题将一道LCT的题特殊化（支持加边和删边，询问图的连通性），将图变成了2×m的网格图，然后就神奇地可以用线段树来维护。
对于每个区间[l,r]，维护其四个角落之间的连通性（仅仅通过[l,r]这段的边构建起的连通性）。
查询[l,r]时，先计算出[1,l-1],[l,r],[r+1,c]这三个线段的连通性，然后将[l,r]的四个角变成并查集的4个点，先用[l,r]中的6种关系更新，在看是否可以从左上角的点通过左边区间绕道左下角，以及从右上角通过右边区间绕道右下角，该并的并起来后直接看查询的点是否在一个集合即可。
/**************************************************************
Problem: 1018
User: idy002
Language: C++
Result: Accepted
Time:1472 ms
Memory:2840 kb
****************************************************************/ #include <cstdio>
#include <iostream>
#define maxn 100010
#define AB 1
#define AC 2
#define AD 4
#define BC 8
#define BD 16
#define CD 32
using namespace std; // a b
// c d typedef unsigned Stat; Stat stat[maxn];
int son[maxn][], ntot, root; int c;
bool er[][maxn], ed[maxn]; Stat merge( Stat l, Stat r, int mid ) {
Stat ab = ((l&AB)&&(r&AB)&&er[][mid]) || ((l&AD)&&(r&BC)&&er[][mid]) ? AB : ;
Stat cd = ((l&CD)&&(r&CD)&&er[][mid]) || ((l&BC)&&(r&AD)&&er[][mid]) ? CD : ;
Stat ad = ((l&AB)&&(r&AD)&&er[][mid]) || ((l&AD)&&(r&CD)&&er[][mid]) ? AD : ;
Stat bc = ((l&CD)&&(r&BC)&&er[][mid]) || ((l&BC)&&(r&AB)&&er[][mid]) ? BC : ;
Stat ac = (l&AC) || ((l&AB)&&(l&CD)&&(er[][mid])&&(er[][mid])&&(r&AC)) ? AC : ;
Stat bd = (r&BD) || ((r&AB)&&(r&CD)&&(er[][mid])&&(er[][mid])&&(l&BD)) ? BD : ;
return ab | ac | ad | bc | bd | cd;
}
void update( int nd, int lf, int rg ) {
stat[nd] = merge( stat[son[nd][]], stat[son[nd][]], (lf+rg)>> );
}
int build( int lf, int rg ) {
if( lf>rg ) return ;
int nd = ++ntot;
if( lf==rg ) {
stat[nd] = AB | CD;
return nd;
}
int mid = (lf+rg)>>;
son[nd][] = build( lf, mid );
son[nd][] = build( mid+, rg );
update( nd, lf, rg );
return nd;
}
void modify( int x, int nd, int lf, int rg ) {
if( lf==rg ) {
stat[nd] = AB | CD;
if( ed[lf] )
stat[nd] |= AC | BD | AD | BC;
return;
}
int mid = (lf+rg)>>;
if( x<=mid ) modify(x,son[nd][],lf,mid);
else modify(x,son[nd][],mid+,rg);
update(nd,lf,rg);
}
Stat query( int L, int R, int nd, int lf, int rg ) {
if( L<=lf&&rg<=R ) return stat[nd];
int mid = (lf+rg)>>;
if( R<=mid ) return query( L, R, son[nd][], lf, mid );
if( L>mid ) return query( L, R, son[nd][], mid+, rg );
Stat lstat = query( L, R, son[nd][], lf, mid );
Stat rstat = query( L, R, son[nd][], mid+, rg );
return merge(lstat,rstat,mid);
} int fa[];
void init() {
for( int i=; i<=; i++ ) fa[i]=i;
}
int find( int i ) {
return fa[i]==i ? i : fa[i]=find(fa[i]);
}
void unon( int a, int b ) {
a = find(a);
b = find(b);
fa[a] = b;
}
int main() {
scanf( "%d", &c );
root = build( , c );
while() {
char ch[]; scanf( "%s", ch );
if( ch[]=='E' ) return ;
int ax, ay, bx, by;
scanf( "%d%d%d%d", &ax, &ay, &bx, &by ); if( ch[]=='A' ) {
if( ay>by ) {
swap( ax, bx );
swap( ay, by );
}
Stat sl=, sc=, sr=;
if( ay> ) sl = query(,ay-,root,,c);
sc = query(ay,by,root,,c);
if( by<c ) sr = query(by+,c,root,,c); init();
if( sc&AB ) unon( , );
if( sc&AC ) unon( , );
if( sc&AD ) unon( , );
if( sc&BC ) unon( , );
if( sc&BD ) unon( , );
if( sc&CD ) unon( , );
if( (sl&BD) && er[][ay-] && er[][ay-] ) unon( , );
if( (sr&AC) && er[][by] && er[][by] ) unon( , ); bool ok = false;
if( ax== && bx== ) {
ok = find( ) == find( );
} else if( ax== && bx== ) {
ok = find( ) == find( );
} else if( ax== && bx== ) {
ok = find( ) == find( );
} else if( ax== && bx== ) {
ok = find( ) == find( );
} printf( "%s\n", ok ? "Y" : "N" );
} else {
bool *p;
if( ax==bx ) {
p = &er[ax][min(ay,by)];
} else {
p = &ed[ay];
}
*p = ch[]=='O';
modify( ay, root, , c );
if( ay!=by )
modify( by, root, , c );
}
}
}