2004. [USACO Open07] 连接

【题目描述】

稍有常识的人都知道，加拿大有两个季节：冬季和修路季。在全球变暖之前的好日子里，修路季是七月，而冬季包含其余全部11个月份。由于地球正在变暖，修路季现在变成了从四月开始直到九月。

这对于驼鹿而言是个坏消息，因为它们使用道路网络作为主要的交通方式，然而现在一年中的六个月，而非一个月内，许多道路都不堪使用。加拿大驼鹿Canmuu希望建立一套旅行日程表系统，它知道所有道路的状态，并且能告诉驼鹿，它们是否能沿着道路在城市间旅行。驼鹿们有点傻，因此它们在旅途中经过的道路必须完全落在起点和终点所在两列夹成的区间内。

Canmuu意识到，加拿大所有重要的道路交叉点（通常是城市）可以视作一张网格，道路则连接（且只会连接）着相邻的格点。他画了一张矩形网格，有$R（1<=R<=2）行，C（1<=C<=15000）$列，其中的每个格点代表一个道路交叉点。下图是这种网格的一个例子，代表了南安大略地区（*号代表未连接的空位置，例如农场）：

在这个例子中，虽然从滑铁卢到奥兰治维尔有一条路径，但没有可接受的路径，因为驼鹿们必须经过多伦多（译者注：多伦多位于第3列，超过了滑铁卢和奥兰治维尔的[1,2]列范围）。如果从林德赛到金斯敦的道路关闭了，那么从滑铁卢就不再能够到达金斯敦（或从任何地方到达金斯敦）。但如果从多伦多到林德赛的路径关闭了，我们仍然能从滑铁卢走到金斯敦。

为方便参考，城市被记作(行,列)数对，因此上图变成了：

Canmuu创建了一个网络，支持对驼鹿旅行日程表的实时修改。他还设计了一套系统来告知日程表已存在的N条道路；这些道路位于输入文件中（见下面的描述）。

实时修改由输入中的若干行给出，每行为如下格式之一：

C $r_1 \quad c_1\quad r_2\quad c_2$ 连接相邻点$(r_1,c_1)$和$(r_2,c_2)$的道路正在维修，关闭了。

O $r_1 \quad c_1\quad r_2\quad c_2$ 连接相邻点$(r_1,c_1)$和$(r_2,c_2)$的道路现在开放。这可能意味着修建了一条新路，或一条道路已维修完成。

T $r_1 \quad c_1\quad r_2\quad c_2$ 一头驼鹿希望沿道路从（可能不相邻的）节点$(r_1,c_1)$旅行到$(r_2,c_2)$，途中不走到$c_1-c_2$列之外。输出Y代表可行，N代表不可行。

E         程序结束。

实现一个程序，读入道路网络，并处理之后的不超过$50000$个操作。

【输入格式】

第1行：一个整数N。

第2~N+1行：第i+1行有四个空格隔开的整数，描述了一条道路两端点的坐标：$(r_1,c_1)$和$(r_2,c_2)$.保证没有重边。

接下来是若干行，每行描述一个操作，一行“E”代表结束。

【输出格式】

对每个T操作，输出一行一个Y或一个N。

【样例输入】

8

1 2 1 3

1 3 1 4

1 3 2 3

1 4 2 4

2 1 2 2

2 2 2 3

2 3 2 4

2 4 2 5

C 2 4 2 5

T 2 1 2 5

T 2 1 1 2

C 2 3 2 4

O 2 4 2 5

T 2 1 2 5

E

【样例输出】

N

N

Y

【提示】

原问题为交互式在线，这里改成了离线，请各位自行注意节操：）

【来源】

Richard Peng,2007