P4246 [SHOI2008]堵塞的交通

    • 274通过
    • 989提交
  • 题目提供者 KSkun
  • 评测方式 云端评测
  • 标签 线段树 递归 各省省选 2008 上海
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    有一天,由于某种穿越现象作用,你来到了传说中的小人国。小人国的布局非常奇特,整个国家的交通系统可以被看成是一个$2$行$C$列的矩形网格,网格上的每个点代表一个城市,相邻的城市之间有一条道路,所以总共有$2C$个城市和$3C-2$条道路。

    小人国的交通状况非常槽糕。有的时候由于交通堵塞,两座城市之间的道路会变得不连通,直到拥堵解决,道路才会恢复畅通。初来咋到的你决心毛遂自荐到交通部某份差事,部长听说你来自一个科技高度发达的世界,喜出望外地要求你编写一个查询应答系统,以挽救已经病入膏肓的小人国交通系统。 小人国的交通部将提供一些交通信息给你,你的任务是根据当前的交通情况回答查询的问题。交通信息可以分为以下几种格式:

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

    注:$r_i$表示行数,$c_i$表示列数,$1 \leq r_i \leq 2, 1 \leq c_i \leq C$。

    输入输出格式

    输入格式:

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

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    2
    Open 1 1 1 2
    Open 1 2 2 2
    Ask 1 1 2 2
    Ask 2 1 2 2
    Exit
    输出样例#1: 复制
    Y
    N

    说明

    数据范围:

    对于100%的数据,$1 \leq C \leq 100000$,$1 \leq$信息条数$\leq 100000$。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。