Description

　　有一天，由于某種穿越現象作用，你來到了傳說中的小人國。小人國的布局非常奇特，整個國家的交通系統可以被看成是一個2行C列的矩形網格，網格上的每個點代表一個城市，相鄰的城市之間有一條道路，所以總共有2C個城市和3C-2條道路。 小人國的交通狀況非常槽糕。有的時候由于交通堵塞，兩座城市之間的道路會變得不連通，直到擁堵解決，道路才會恢復暢通。初來咋到的你決心毛遂自薦到交通部某份差事，部長聽說你來自一個科技高度發達的世界，喜出望外地要求你編寫一個查詢應答系統，以挽救已經病入膏肓的小人國交通系統。 小人國的交通部將提供一些交通信息給你，你的任務是根據當前的交通情況回答查詢的問題。交通信息可以分為以下幾種格式：Close r1 c1 r2 c2：相鄰的兩座城市(r1,c1)和(r2,c2)之間的道路被堵塞了；Open r1 c1 r2 c2：相鄰的兩座城市(r1,c1)和(r2,c2)之間的道路被疏通了；Ask r1 c1 r2 c2：詢問城市(r1,c1)和(r2,c2)是否連通。如果存在一條路徑使得這兩條城市連通，則返回Y，否則返回N；

Input

　　第一行只有一個整數C，表示網格的列數。接下來若干行，每行為一條交通信息，以單獨的一行“Exit”作為結束。我們假設在一開始所有的道路都是堵塞的。我們保證 C小于等于100000，信息條數小于等于100000。

Output

　　對于每個查詢，輸出一個“Y”或“N”。

Sample Input

Sample Output

HINT

 題解：JudgeOnline/upload/201604/sol(4).rar

Source

題解：線段樹維護連通性

對于相鄰兩個點維護6個信息。

需要注意的是查詢的時候，該區間的r1,r2不連通，不一定r1,r2無法連通，所以需要考慮通過兩邊的區間使r1,r2連通的情況。

還有對于單點的修改，所有的值都要重新計算。

#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>#define N 100003using namespace std;int n;struct data {	int l1,l2,h1,h2,r1,r2;//l1,l2,r1,r2是真實存在的，h1,h2每次更改都需要重新推 	data() {		l1=l2=h1=h2=r1=r2=0;	}}tr[N*4],a[N];//l1表示左上角到右上角//l2表示左下角到右下角 //r1表示左上角到左下角 //r2表示右上角到右下角 //h1表示左上角到右下角 //h2表示左下角到右上角 data update(data a,data b){	data t;	t.l1=max(t.l1,a.l1&b.l1); t.l1=max(t.l1,a.h1&b.h2); 	t.l2=max(t.l2,a.l2&b.l2); t.l2=max(t.l2,a.h2&b.h1);	t.r1=a.r1; t.r1=max(t.r1,t.l1&t.l2&b.r2); t.r1=max(t.r1,a.l1&b.r1&a.l2);	t.r2=b.r2; t.r2=max(t.r2,t.l1&t.l2&a.r1); t.r2=max(t.r2,b.l1&b.l2&a.r2);	t.h1=max(t.h1,a.l1&b.h1); t.h1=max(t.h1,a.h1&b.l2);	t.h2=max(t.h2,a.h2&b.l1); t.h2=max(t.h2,a.l2&b.h2);	return t;}void pointchange(int now,int l,int r,int opt,int x,int val)//opt=1 l1;opt=2 l2; opt=3 r1;opt=4 r2;{	if (x==0) return;	if (l==r) {		tr[now].l1=a[l].l1;		tr[now].l2=a[l].l2;		tr[now].r1=a[l].r1;		tr[now].r2=a[l].r2;		tr[now].l1=max(tr[now].l1,tr[now].r1&tr[now].l2&tr[now].r2);		tr[now].l2=max(tr[now].l2,tr[now].r1&tr[now].l1&tr[now].r2);		tr[now].r1=max(tr[now].r1,tr[now].l1&tr[now].r2&tr[now].l2);		tr[now].r2=max(tr[now].r2,tr[now].l1&tr[now].r1&tr[now].l2);		tr[now].h1=max(tr[now].r1&tr[now].l2,tr[now].l1&tr[now].r2);		tr[now].h2=max(tr[now].r1&tr[now].l1,tr[now].l2&tr[now].r2);		return;	}	int mid=(l+r)/2;	if (x<=mid) pointchange(now<<1,l,mid,opt,x,val);	else pointchange(now<<1|1,mid+1,r,opt,x,val);	tr[now]=update(tr[now<<1],tr[now<<1|1]); }data query(int now,int l,int r,int ll,int rr){	data t;	if (rr<ll||!ll) return t;	if (ll<=l&&r<=rr) return tr[now];	int mid=(l+r)/2;  bool pd=false;	if (ll<=mid) t=query(now<<1,l,mid,ll,rr),pd=true;	if (rr>mid)  {		data a=query(now<<1|1,mid+1,r,ll,rr);		if (pd) t=update(t,a);		else t=a;	}	return t;}int main(){	freopen("a.in","r",stdin);	freopen("my.out","w",stdout);	scanf("%d",&n);	while (true) {		char s[10]; scanf("%s",s);		int x,y,x0,y0; scanf("%d%d%d%d",&x0,&y0,&x,&y);		if (y0>y) swap(x0,x),swap(y0,y);		if (s[0]=='E') break;		if(s[0]=='O'||s[0]=='C') {			int opt=0; int t=0; data t1;			if (s[0]=='O') t=1; 			if (x0==x&&x==1) opt=1,a[y0].l1=t,pointchange(1,1,n,1,y0,t);			if (x0==x&&x==2) opt=2,a[y0].l2=t,pointchange(1,1,n,2,y0,t);			if (y0==y){			  a[y].r1=t,pointchange(1,1,n,3,y,t);			  a[y-1].r2=t,pointchange(1,1,n,4,y-1,t);		    }		}		else {			int opt; data t,t1,t2; int pd=false;			if (x==x0&&y==y0) {				PRintf("Y/n");				continue;			}			if (x0==x&&x==1) {			  t1=query(1,1,n,1,y0-1);  t2=query(1,1,n,y,n);			  t=query(1,1,n,y0,y-1),pd=t.l1;			  t.r1=max(t.r1,t1.r2); t.r2=max(t.r2,t2.r1);			  pd=max(pd,t.r1&t.l2&t.r2);		    }			if (x0==x&&x==2){			  t=query(1,1,n,y0,y-1),pd=t.l2;			  t1=query(1,1,n,1,y0-1);  t2=query(1,1,n,y,n);			  t.r1=max(t.r1,t1.r2); t.r2=max(t.r2,t2.r1);			  pd=max(pd,t.r1&t.l1&t.r2);		    }			if (x0==1&&x==2&&y!=y0) {			  t=query(1,1,n,y0,y-1),pd=t.h1;			  t1=query(1,1,n,1,y0-1); t2=query(1,1,n,y,n);			  t.r1=max(t.r1,t1.r2); t.r2=max(t.r2,t2.r1);			  pd=max(pd,t.r1&t.l2); pd=max(pd,t.r2&t.l1);			  pd=max(pd,t.r1&t.h2&t.r2);		    }			if (x0==2&&x==1&&y!=y0) {			  t=query(1,1,n,y0,y-1),pd=t.h2;			  t1=query(1,1,n,1,y0-1);  t2=query(1,1,n,y,n);			  t.r1=max(t.r1,t1.r2); t.r2=max(t.r2,t2.r1);			  pd=max(pd,t.r1&t.l1); pd=max(pd,t.r2&t.l2);			  pd=max(pd,t.r1&t.h1&t.r2);		    }			if (x0!=x&&y==y0) {			 t1=query(1,1,n,1,y0-1);  t2=query(1,1,n,y,n); 			 pd=t1.r2|t2.r1;		    }		    if (pd) printf("Y/n");		    else printf("N/n");		}	}}