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
2 Open 1 1 1 2 Open 1 2 2 2 Ask 1 1 2 2 Ask 2 1 2 2 ExitSample Output
Y N嗯，这题是一道线段树神题。线段树要维护一些信息，维护区间内左上左下，右上右下的连通情况，以及第一行和第二行是否可以向外延伸（共计$luru、lurd、luld、ldru、ldrd、rurd、road[0/1]$8条信息）。
那么我们维护这些信息有什么用呢？
维护这个信息是为了区间合并用的。我们先画个图（如上图），我现在要将两个区间合并。 新的信息如何维护？\(lu1\)-->\(ru2:lu1\)-->\(ru1\)+第一行连通+\(lu2\)-->\(ru2\)\(lu1\)-->\(ru2:lu1\)-->\(rd1\)+第二行连通+\(ld2\)-->\(ru2\) 上面我列举了\(lu1\)-->\(ru2\)的情况，其他的7中情况都有类似的合并方式，我就不一一列举了，对这代码和图就能理解。 至于如何判断连通？同样对着代码和图理解下即可。 (ps：附上一图，以便check理解)
/*program from Wolfycz*/#include#include #include #include #include #define inf 0x7f7f7f7fusing namespace std;typedef long long ll;typedef unsigned int ui;typedef unsigned long long ull;inline char gc(){ static char buf[1000000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;}inline int frd(){ int x=0,f=1; char ch=gc(); for (;ch<'0'||ch>'9';ch=gc()) if (ch=='-') f=-1; for (;ch>='0'&&ch<='9';ch=gc()) x=(x<<3)+(x<<1)+ch-'0'; return x*f;}inline int read(){ int x=0,f=1; char ch=getchar(); for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1; for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+ch-'0'; return x*f;}inline void print(int x){ if (x<0) putchar('-'),x=-x; if (x>9) print(x/10); putchar(x%10+'0');}const int N=1e5;int n;struct S1{ #define ls (p<<1) #define rs (p<<1|1) struct node{ bool luru,lurd,luld,ldru,ldrd,rurd;//6种连通方式 bool road[2]; node(){luru=lurd=luld=ldru=ldrd=rurd=road[0]=road[1]=0;} void init(){luru=ldrd=1;} void insert(int type){lurd=luld=ldru=rurd=type;} }tree[(N<<2)+10]; friend node operator +(const node &x,const node &y){ node z; memcpy(z.road,y.road,sizeof(y.road));//因为是向右边打通，所以找右边哪个 if ((x.luru&&x.road[0]&&y.luru)||(x.lurd&&x.road[1]&&y.ldru)) z.luru=1; if ((x.luru&&x.road[0]&&y.lurd)||(x.lurd&&x.road[1]&&y.ldrd)) z.lurd=1; if ((x.ldru&&x.road[0]&&y.luru)||(x.ldrd&&x.road[1]&&y.ldru)) z.ldru=1; if ((x.ldru&&x.road[0]&&y.lurd)||(x.ldrd&&x.road[1]&&y.ldrd)) z.ldrd=1; if ((x.luld)||(x.luru&&x.road[0]&&y.luld&&x.road[1]&&x.ldrd)) z.luld=1; if ((y.rurd)||(y.luru&&x.road[0]&&x.rurd&&x.road[1]&&y.ldrd)) z.rurd=1; //更新的话自己照着图理解 return z; } void build(int p,int l,int r){ if (l==r){ tree[p].init(); return; } int mid=(l+r)>>1; build(ls,l,mid),build(rs,mid+1,r); } void insert(int p,int l,int r,int x,int mode,bool v){ if (l==r){ if (!mode) tree[p].insert(v); else tree[p].road[mode-1]=v; return; } int mid=(l+r)>>1; if (x<=mid) insert(ls,l,mid,x,mode,v); else insert(rs,mid+1,r,x,mode,v); tree[p]=tree[ls]+tree[rs]; } node Query(int p,int l,int r,int x,int y){ if (x<=l&&r<=y) return tree[p]; int mid=(l+r)>>1; if (y<=mid) return Query(ls,l,mid,x,y); if (x>mid) return Query(rs,mid+1,r,x,y); return Query(ls,l,mid,x,y)+Query(rs,mid+1,r,x,y); } bool check(){ int r1=read(),c1=read(),r2=read(),c2=read(); if (c1>c2) swap(c1,c2),swap(r1,r2); node pre=Query(1,1,n,1,c1); node now=Query(1,1,n,c1,c2); node nxt=Query(1,1,n,c2,n); //pre的右边和now的左边是重合的，now的右边和las的左边是重合的。不过pre记录的是1~c1的联通情况，和now不同，所以要分3个区间讨论 if (r1==r2){//讨论自己按着图理解一下 if ((r1==1)&&((now.luru)||(pre.rurd&&now.ldru)||(now.lurd&&nxt.luld)||(pre.rurd&&now.ldrd&&nxt.luld))) return 1; if ((r1==2)&&((now.ldrd)||(pre.rurd&&now.lurd)||(now.ldru&&nxt.luld)||(pre.rurd&&now.luru&&nxt.luld))) return 1; }else{ if ((r1==1)&&((now.lurd)||(pre.rurd&&now.ldrd)||(now.luru&&nxt.luld)||(pre.rurd&&now.ldru&&nxt.luld))) return 1; if ((r1==2)&&((now.ldru)||(pre.rurd&&now.luru)||(now.ldrd&&nxt.luld)||(pre.rurd&&now.lurd&&nxt.luld))) return 1; } return 0; } #undef ls #undef rs}ST;//Segment Tree;int main(){ n=read(); char s[10]; ST.build(1,1,n); while (true){ scanf("%s",s); if (s[0]=='E') break; if (s[0]=='A') printf(ST.check()?"Y\n":"N\n"); if (s[0]=='C'||s[0]=='O'){ int r1=read(),c1=read(),r2=read(),c2=read(); if (c1==c2) ST.insert(1,1,n,c1,0,s[0]=='O'); if (r1==r2) ST.insert(1,1,n,min(c1,c2),r1,s[0]=='O'); } } return 0;}