记录编号	167744	评测结果	AAAAAAAAA
题目名称	[USACO Open07] 连接	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.228 s
提交时间	2015-06-28 13:58:43	内存使用	0.77 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define Nil NULL
const int MAXC=15000;
class Mat2{//普通的矩阵我们普通的摇......
public:
	int s[2][2];
	Mat2(int x=0){
		s[0][0]=s[1][1]=x;
		s[0][1]=s[1][0]=0;
	}
	Mat2(int x,int y){
		s[0][0]=s[1][1]=x;
		s[0][1]=s[1][0]=y;
	}
};
Mat2 operator * (const Mat2 &a,const Mat2 &b){
	Mat2 c;
	for(int i=0;i<2;i++){
		for(int j=0;j<2;j++){
			c.s[i][j]=0;
			for(int k=0;k<2;k++){
				c.s[i][j]|=a.s[i][k]&&b.s[k][j];
			}
		}
	}
	return c;
}
Mat2 I2(1);//2*2单位阵
Mat2 horizon[MAXC+10];
Mat2 vertical[MAXC+10];
class Node{
public:
	int l,r;
	int mid;
	Node *lc,*rc;
	Mat2 con;
	void push_up(void){
		if(lc!=Nil){
			con=lc->con*horizon[mid]*rc->con;//听说是右结合?反正对称阵无影响
		}
	}
	void modify(int x,const Mat2 &t){//将x列的上下连通性修改为t
		if(l>x||r<x) return;
		if(l==x&&r==x) con=t;
		else{
			lc->modify(x,t);
			rc->modify(x,t);
			push_up();
		}
	}
	Mat2 query(int a,int b){
		if(l>b||r<a) return I2;
		if(l>=a&&r<=b) return con;
		else if(b<=mid) return lc->query(a,b);
		else if(a>mid) return rc->query(a,b);
		return lc->query(a,b)*horizon[mid]*rc->query(a,b);
	}
};
Node* build(int l,int r){
	Node *p=new Node;
	p->l=l,p->r=r;
	p->mid=(l+r)/2;
	if(l==r){
		p->lc=p->rc=Nil;
		p->con=vertical[l];
	}
	else{
		p->lc=build(l,p->mid);
		p->rc=build(p->mid+1,r);
		p->push_up();
	}
	return p;
}
Node *root;
void modify(int r1,int c1,int r2,int c2,int t){//道路状况修改为t
	if(r1==r2){//水平道路
		if(c1>c2) swap(c1,c2);
		horizon[c1].s[r1][r1]=t;
		root->modify(c1,vertical[c1]);
	}
	else if(c1==c2){//竖直道路
		vertical[c1]=Mat2(1,t);
		root->modify(c1,vertical[c1]);
	}
}
bool query(int r1,int c1,int r2,int c2){
	if(c1>c2){
		swap(r1,r2);
		swap(c1,c2);
	}
	Mat2 c=root->query(c1,c2);
	return c.s[r1][r2];
}
void work(void){
	char cmd[10];
	int r1,c1,r2,c2;
	while(true){
		scanf("%s",cmd);
		if(cmd[0]=='E') break;
		else if(cmd[0]=='C'){
			scanf("%d%d%d%d\n",&r1,&c1,&r2,&c2);
			modify(r1-1,c1-1,r2-1,c2-1,0);
		}
		else if(cmd[0]=='O'){
			scanf("%d%d%d%d\n",&r1,&c1,&r2,&c2);
			modify(r1-1,c1-1,r2-1,c2-1,1);
		}
		else if(cmd[0]=='T'){
			scanf("%d%d%d%d\n",&r1,&c1,&r2,&c2);
			if(query(r1-1,c1-1,r2-1,c2-1)) printf("Y\n");
			else printf("N\n");
		}
	}
}
void init_graph(void){
	int M;
	scanf("%d",&M);
	int r1,c1,r2,c2;
	for(int i=0;i<MAXC;i++) vertical[i]=Mat2(1,0);
	for(int i=1;i<=M;i++){
		scanf("%d%d%d%d\n",&r1,&c1,&r2,&c2);
		r1--,c1--,r2--,c2--;
		if(r1==r2){//水平线
			if(c1>c2) swap(c1,c2);
			horizon[c1].s[r1][r1]=1;
		}
		else if(c1==c2){//竖直线
			vertical[c1]=Mat2(1,1);
		}
	}
	root=build(0,MAXC-1);
}
int main(){
	freopen("connect.in","r",stdin);
	freopen("connect.out","w",stdout);
	init_graph();
	work();
	return 0;
}