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”作为结束。我们假设在一开始所有的道路都是堵塞的。 对30%测试数据，我们保证C小于等于1000，信息条数小于等于1000； 对100%测试数据，我们保证 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
Exit

Sample Output

Y
N

HINT

线段树维护区间连通性。（懒癌犯了，一句话题解。。。）

#include <bits/stdc++.h>
#define N 100010
using namespace std;

struct DAT
{
    bool v[2],s[2],x[2];
}dat[N<<2];

bool a[N][2][2];
int n,r1,r2,c1,c2;
int dx[3]={-1,0,1};
int dy[3]={0,1,0};

inline void build(int u,int l,int r)
{
    if(l == r) {dat[u].s[0] = dat[u].s[1] = true; return;}
    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
}

inline void pack(DAT &u,DAT &ls,DAT &rs,int mid)
{
    u.x[0] = ls.x[0]||(ls.s[0]&&a[mid][0][0]&&rs.x[0]&&a[mid][1][0]&&ls.s[1]);//左上-右上 
    u.x[1] = rs.x[1]||(rs.s[0]&&a[mid][0][0]&&ls.x[1]&&a[mid][1][0]&&rs.s[1]);//左下-右下 
    u.s[0] = (ls.s[0]&&a[mid][0][0]&&rs.s[0])||(ls.v[0]&&a[mid][1][0]&&rs.v[1]);//左上-左下
    u.s[1] = (ls.s[1]&&a[mid][1][0]&&rs.s[1])||(ls.v[1]&&a[mid][0][0]&&rs.v[0]);//右上-右下
    u.v[0] = (ls.s[0]&&a[mid][0][0]&&rs.v[0])||(ls.v[0]&&a[mid][1][0]&&rs.s[1]);//左上-右下
    u.v[1] = (ls.s[1]&&a[mid][1][0]&&rs.v[1])||(ls.v[1]&&a[mid][0][0]&&rs.s[0]);//右上-左下 
}

inline void updata(int u,int l,int r,int p)
{
    if(l == r)
    {
        dat[u].x[0] = dat[u].x[1] = dat[u].v[1] = dat[u].v[0] = a[p][0][1];
        dat[u].s[0] = dat[u].s[1] = true;
        return;
    }
    int mid = (l + r) >> 1;
    if(p <= mid) updata(u << 1, l, mid, p);
    else updata(u << 1 | 1, mid + 1, r, p);
    pack(dat[u], dat[u << 1], dat[u << 1 | 1], mid);
}

inline void change(bool pd)
{
    if(r1 > r2) swap(r1,r2),swap(c1,c2);
    int dir;
    for(int i = 0; i < 3; i ++)
        if(c1 + dx[i] == c2 && r1 + dy[i] == r2) dir = i;
    if(dir == 0) a[c2][r2][0] = pd,updata(1,1,n,c2);
    else if(dir == 1) a[c1][0][1] = pd,updata(1,1,n,c1);
    else a[c1][r1][0] = pd, updata(1,1,n,c1);
}

inline void getpack(DAT &p,int u,int L,int R,int l,int r)
{
    if(l <=L&&r>=R) {p=dat[u];return;}
    int mid=(L+R)>>1;
    if(r<=mid) getpack(p,u<<1,L,mid,l,r);
    else if(l>=mid+1) getpack(p,u<<1|1,mid+1,R,l,r);
    else
    {
        DAT tmp1,tmp2;
        getpack(tmp1,u<<1,L,mid,l,mid);
        getpack(tmp2,u<<1|1,mid+1,R,mid+1,r);
        pack(p,tmp1,tmp2,mid);
    }
}

inline void getans()
{
    if(c1>c2) swap(c1,c2),swap(r1,r2);
    DAT pa,pb,pc;
    getpack(pa,1,1,n,1,c1);
    getpack(pb,1,1,n,c1,c2);
    getpack(pc,1,1,n,c2,n);
    if(r1 == r2)
        if(r1 == 0)
        {
            if(pb.s[0] || (pa.x[1] && pb.v[1]) || (pc.x[0] && pb.v[0]) || (pa.x[1] && pb.s[1] && pc.x[0])) puts("Y");
            else puts("N");
        }
        else
        {
            if(pb.s[1] || (pa.x[1] && pb.v[0]) || (pc.x[0] && pb.v[1]) || (pa.x[1] && pb.s[0] && pc.x[0])) puts("Y");
            else puts("N");
        }
    else
        if(r1 == 0)
        {
            if(pb.v[0] || (pa.x[1] && pb.s[1]) || (pc.x[0] && pb.s[0])) puts("Y");
            else puts("N");
        }
        else
        {
            if(pb.v[1] || (pa.x[1] && pb.s[0]) || (pc.x[0] && pb.s[1])) puts("Y");
            else puts("N");
        }
}

int main()
{
    char str[10];
    scanf("%d",&n);
    build(1,1,n);
    while(scanf("%s",str))
    {
        if(str[0] == 'E') break;
        scanf("%d%d%d%d",&r1,&c1,&r2,&c2);
        r1 --;
        r2 --;
        if(str[0] == 'O') change(1);
        else if(str[0] == 'C') change(0);
        else getans();
    }
    return 0;
}