显示代码纯文本
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstdlib>
using namespace std;
const int INF = 0x7fffffff;
const int MAXN = 100001;
int n; bool a[MAXN][3];
// a[i][0] (0,i)<->(0,i+1)
// a[i][1] (1,i)<->(1,i+1)
// a[i][2] (0,i)<->(1,i)
namespace SGT {
struct State {
int s[6];
// 0 (0,0)<->(0,1)
// 1 (1,0)<->(1,1)
// 2 (0,0)<->(1,0)
// 3 (0,1)<->(1,1)
// 4 (0,0)<->(1,1)
// 5 (1,0)<->(0,1)
State() {}
State( const State &rhs ) {
for( int i = 0; i < 6; ++i ) s[i] = rhs.s[i];
}
int& operator[]( int idx ) { return s[idx]; }
};
State arr[MAXN<<2];
const int id12 = 0;
const int id34 = 1;
const int id13 = 2;
const int id24 = 3;
const int id14 = 4;
const int id23 = 5;
inline int id( int x1, int y1, int x2, int y2 ) {
if( ( x1 == 0 && y1 == 0 && x2 == 0 && y2 == 1 ) ||
( x1 == 0 && y1 == 1 && x2 == 0 && y2 == 0 ) ) return id12;
if( ( x1 == 1 && y1 == 0 && x2 == 1 && y2 == 1 ) ||
( x1 == 1 && y1 == 1 && x2 == 1 && y2 == 0 ) ) return id34;
if( ( x1 == 0 && y1 == 0 && x2 == 1 && y2 == 0 ) ||
( x1 == 1 && y1 == 0 && x2 == 0 && y2 == 0 ) ) return id13;
if( ( x1 == 0 && y1 == 1 && x2 == 1 && y2 == 1 ) ||
( x1 == 1 && y1 == 1 && x2 == 0 && y2 == 1 ) ) return id24;
if( ( x1 == 0 && y1 == 0 && x2 == 1 && y2 == 1 ) ||
( x1 == 1 && y1 == 1 && x2 == 0 && y2 == 0 ) ) return id14;
if( ( x1 == 1 && y1 == 0 && x2 == 0 && y2 == 1 ) ||
( x1 == 0 && y1 == 1 && x2 == 1 && y2 == 0 ) ) return id23;
return INF;
}
void _init( int o, int L, int R ) {
if( L == R ) {
arr[o][id12] = arr[o][id34] = true;
return;
}
int M = (L+R)>>1; int lc = o<<1; int rc = lc|1;
_init(lc,L,M); _init(rc,M+1,R);
}
void init() {
memset( arr, 0, sizeof(arr) );
_init(1,1,n);
}
int col;
State merge( State L, State R, int M ) {
State rtn;
rtn[id12] = ( L[id12] && a[M][0] && R[id12] ) || ( L[id14] && a[M][1] && R[id23] );
rtn[id34] = ( L[id34] && a[M][1] && R[id34] ) || ( L[id23] && a[M][0] && R[id14] );
rtn[id13] = L[id13] || ( L[id12] && a[M][0] && R[id13] && a[M][1] && L[id34] );
rtn[id24] = R[id24] || ( R[id12] && a[M][0] && L[id24] && a[M][1] && R[id34] );
rtn[id14] = ( L[id12] && a[M][0] && R[id14] ) || ( L[id14] && a[M][1] && R[id34] );
rtn[id23] = ( L[id34] && a[M][1] && R[id23] ) || ( L[id23] && a[M][0] && R[id12] );
return rtn;
}
void maintain( int o, int L, int R ) {
int M = (L+R)>>1; int lc = o<<1; int rc = lc|1;
arr[o] = merge( arr[lc], arr[rc], M );
}
void _update( int o, int L, int R ) {
if( L == R ) {
arr[o][id13] = arr[o][id24] = arr[o][id14] = arr[o][id23] = a[L][2];
return;
}
int M = (L+R)>>1; int lc = o<<1; int rc = lc|1;
if( col <= M ) _update(lc,L,M); else _update(rc,M+1,R);
maintain(o,L,R);
}
void update( int y ) {
col = y; _update(1,1,n);
}
int left, right;
State _query( int o, int L, int R ) {
if( L >= left && R <= right ) return arr[o];
int M = (L+R)>>1; int lc = o<<1; int rc = lc|1;
if( left <= M && right > M )
return merge( _query(lc,L,M), _query(rc,M+1,R), M );
else if( right <= M ) return _query(lc,L,M);
else return _query(rc,M+1,R); // left > M
}
State query( int l, int r ) {
left = l; right = r; return _query(1,1,n);
}
}
namespace Solve {
void open( int x1, int y1, int x2, int y2 ) {
--x1; --x2;
if( y1 == y2 ) {
a[y1][2] = true; SGT::update(y1);
} else {
if( y1 > y2 ) swap(y1,y2);
a[y1][x1] = true; SGT::update(y1);
}
}
void close( int x1, int y1, int x2, int y2 ) {
--x1; --x2;
if( y1 == y2 ) {
a[y1][2] = false; SGT::update(y1);
} else {
if( y1 > y2 ) swap(y1,y2);
a[y1][x1] = false; SGT::update(y1);
}
}
void ask( int x1, int y1, int x2, int y2 ) {
--x1; --x2;
if( y1 > y2 ) {
swap(y1,y2); swap(x1,x2);
}
using SGT::State; using SGT::query; using SGT::id;
State p = query(1,y1), r = query(y1,y2), q = query(y2,n);
if( r[id(x1,0,x2,1)] ) { printf( "Y\n" ); return; } // 直接到达
bool left = r[id(0,0,1,0)] || p[id(0,1,1,1)]; // 走左边
if( left && r[id(x1^1,0,x2,1)] ) { printf( "Y\n" ); return; } // 从左边拐回来
bool right = r[id(0,1,1,1)] || q[id(0,0,1,0)]; // 走右边
if( right && r[id(x1,0,x2^1,1)] ) { printf( "Y\n" ); return; } // 从右边拐回来
if( left && right && r[id(x1^1,0,x2^1,1)] ) { printf( "Y\n" ); return; }
printf( "N\n" );
}
}
int main() {
freopen( "bzoj_1018.in", "r", stdin );
freopen( "bzoj_1018.out", "w", stdout );
scanf( "%d", &n ); memset( a, false, sizeof(a) ); SGT::init();
while(1) {
char ord[10]; scanf( "%s", ord );
if( ord[0] == 'E' ) break;
int x1,y1,x2,y2; scanf( "%d%d%d%d", &x1, &y1, &x2, &y2 );
if( ord[0] == 'O' ) Solve::open(x1,y1,x2,y2);
else if( ord[0] == 'C' ) Solve::close(x1,y1,x2,y2);
else Solve::ask(x1,y1,x2,y2);
}
return 0;
}
__stdcall