记录编号	255328	评测结果	AAAAAAAAAA
题目名称	[SHOI 2008]堵塞的交通traffic	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	0.443 s
提交时间	2016-04-27 16:39:12	内存使用	3.34 MiB

/*
很快想到了线段树，但实现起来遇到了困难。。。。。。
思路：
(1)首先，线段树的节点保存[L,R]区间两端的四个格子的连通情况，
共六种,另外还要保存[L,mid],[mid+1,R]
这两段之间的连通情况，即格子(1,mid)和(1,mid+1)
以及(2,mid)和(2,mid+1)是否连接；

(2)查询[L,R]时，有可能L直接与R相连，
也有可能L向前走再回来，或者R向后走再回来。
查询p=[1,L],r=[L,R],q=[R,n]。
那么p的右侧两个格子相连或者r的左侧两个格子相连，
则r的左侧两个格子相连；
q的左侧两个格子相连或者r的右侧两个格子相连，
则r的右侧两个格子相连。
此时利用r的四个格子的连通情况就可以判断
询问的两个格子是否连通。

(3)修改时，x1=x2，
则两个格子为同一行相邻格子，
否则为同一列的两个格子。
*/
#include<stdio.h>
inline void in(int &x){for(x=getchar();x<48||x>57;x=getchar());x^=48;for(int tmp=getchar();47<tmp&&tmp<58;tmp=getchar())x=(x<<1)+(x<<3)+(tmp^48);}
struct node{bool o[6],up,down;}o[400010];
int n,x1,y1,x2,y2;
char s[10];
inline node merge(const node &a,const node &b){
	node an;
	an.up=b.up,an.down=b.down;
	an.o[0]=(a.o[0]&&a.up&&b.o[0])||(a.o[2]&&a.down&&b.o[3]);//(0,0)-(0,1)
	an.o[1]=a.o[1]||(a.o[0]&&a.up&&b.o[1]&&a.down&&a.o[4]);//(0,0)-(1,0)
	an.o[2]=(a.o[0]&&a.up&&b.o[2])||(a.o[2]&&a.down&&b.o[4]);//(0,0)-(1,1)
	an.o[3]=(a.o[4]&&a.down&&b.o[3])||(a.o[3]&&a.up&&b.o[0]);//(1,0)-(0,1)
	an.o[4]=(a.o[4]&&a.down&&b.o[4])||(a.o[3]&&a.up&&b.o[2]);//(1,0)-(1,1)
	an.o[5]=b.o[5]||(b.o[0]&&a.up&&a.o[5]&&a.down&&b.o[4]);//(1,1)-(0,1)
	return an;
}
inline void build(int l,int r,int t){
	if(l==r){
		o[t].o[0]=o[t].o[4]=1;
		return;
	}
	int mid=l+r>>1;
	build(l,mid,t<<1);
	build(mid+1,r,t<<1|1);
}
inline void modify(int l,int r,int t,int x1,int y1,int x2,int y2,bool op){
	if(l==r){
		if(x1!=x2&&y1==y2)o[t].o[1]=o[t].o[2]=o[t].o[3]=o[t].o[5]=op;
		if(x1==x2&&x1==1)o[t].up=op;
		if(x1==x2&&x1==2)o[t].down=op;
		return;
	}
	int mid=l+r>>1;
	if(y1<=mid)modify(l,mid,t<<1,x1,y1,x2,y2,op);
	else modify(mid+1,r,t<<1|1,x1,y1,x2,y2,op);
	o[t]=merge(o[t<<1],o[t<<1|1]);
}
inline node query(int l,int r,int t,int L,int R){
	if(L<=l&&r<=R)return o[t];
	int mid=l+r>>1;
	if(R<=mid)return query(l,mid,t<<1,L,R);
	if(L>mid)return query(mid+1,r,t<<1|1,L,R);
	return merge(query(l,mid,t<<1,L,R),query(mid+1,r,t<<1|1,L,R));
}
int main(){
	freopen("bzoj_1018.in","r",stdin);
	freopen("bzoj_1018.out","w",stdout);
	for(in(n),build(1,n,1),scanf("%s",s);*s!='E';scanf("%s",s)){
		in(x1),in(y1),in(x2),in(y2);
		if(*s=='O'){
			if(x1>x2)x1^=x2,x2^=x1,x1^=x2;
			if(y1>y2)y1^=y2,y2^=y1,y1^=y2;
			modify(1,n,1,x1,y1,x2,y2,1);
		}else if(*s=='C'){
			if(x1>x2)x1^=x2,x2^=x1,x1^=x2;
			if(y1>y2)y1^=y2,y2^=y1,y1^=y2;
			modify(1,n,1,x1,y1,x2,y2,0);
		}else{
			if(y1>y2)x1^=x2,x2^=x1,x1^=x2,y1^=y2,y2^=y1,y1^=y2;
			node ans=query(1,n,1,y1,y2),x=query(1,n,1,1,y1),y=query(1,n,1,y2,n);
			if(x1==x2&&x1==1)puts(ans.o[0]||(x.o[5]&&ans.o[3])||(ans.o[2]&&y.o[1])||(x.o[5]&&ans.o[4]&&y.o[1])?"Y":"N");
			if(x1==x2&&x1==2)puts(ans.o[4]||(x.o[5]&&ans.o[2])||(ans.o[3]&&y.o[1])||(x.o[5]&&ans.o[0]&&y.o[1])?"Y":"N");
			if(x1==1&&x2==2)puts(ans.o[2]||(x.o[5]&&ans.o[4])||(ans.o[0]&&y.o[1])?"Y":"N");
			if(x1==2&&x2==1)puts(ans.o[3]||(x.o[5]&&ans.o[0])||(ans.o[4]&&y.o[1])?"Y":"N");
		}
	}
	//while(1);
}