#2153. [SHOI2008]堵塞的交通traffic

[SHOI2008]堵塞的交通traffic

题目描述

有一天,由于某种穿越现象作用,你来到了传说中的小人国。

小人国的布局非常奇特,整个国家的交通系统可以被看成是一个 22cc 列的矩形网格,网格上的每个点代表一个城市,相邻的城市之间有一条道路,所以总共有 2c2c 个城市和 3c23c - 2 条道路。小人国的交通状况非常槽糕。有的时候由于交通堵塞,两座城市之间的道路会变得不连通,直到拥堵解决,道路才会恢复畅通。

初来乍到的你决心毛遂自荐到交通部某份差事,部长听说你来自一个科技高度发达的世界,喜出望外地要求你编写一个查询应答系统,以挽救已经病入膏肓的小人国交通系统。

小人国的交通部将提供一些交通信息给你,你的任务是根据当前的交通情况回答查询的问题。交通信息可以分为以下几种格式:

  1. Close r1 c1 r2 c2\text{Close}\ r_1\ c_1\ r_2\ c_2:相邻的两座城市 (r1,c1)(r_1, c_1)(r2,c2)(r_2, c_2) 之间的道路被堵塞了;
  2. Open r1 c1 r2 c2\text{Open}\ r_1\ c_1\ r_2\ c_2:相邻的两座城市 (r1,c1)(r_1, c_1)(r2,c2)(r_2, c_2) 之间的道路被疏通了;
  3. Ask r1 c1 r2 c2\text{Ask}\ r_1\ c_1\ r_2\ c_2:询问城市 (r1,c1)(r_1, c_1)(r2,c2)(r_2, c_2) 是否连通。如果存在一条路径使得这两条城市连通,则返回 Y,否则返回 N

输入格式

第一行只有一个整数 cc,表示网格的列数。接下来若干行,每行为一条交通信息,以单独的一行 Exit 作为结束。我们假设在一开始所有的道路都是堵塞的。

输出格式

对于每个查询,输出一个 YN

2
Open 1 1 1 2
Open 1 2 2 2
Ask 1 1 2 2
Ask 2 1 2 2
Exit
Y
N

提示

题解:JudgeOnline/upload/201604/sol(4).rar

数据规模与约定

1c1051 \le c \le 10^5,信息条数 105\le 10^5