CF319E.Ping-Pong

NOI/NOI+/CTSC

通过率:0%

时间限制:2.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

In this problem at each moment you have a set of intervals. You can move from interval (a, b) from our set to interval (c, d) from our set if and only if c < a < d or c < b < d. Also there is a path from interval _I_1 from our set to interval _I_2 from our set if there is a sequence of successive moves starting from _I_1 so that we can reach _I_2.

Your program should handle the queries of the following two types:

  1. "1 x y" (x < y) — add the new interval (x, y) to the set of intervals. The length of the new interval is guaranteed to be strictly greater than all the previous intervals.
  2. "2 a b" (a ≠ b) — answer the question: is there a path from a-th (one-based) added interval to b-th (one-based) added interval?

Answer all the queries. Note, that initially you have an empty set of intervals.

本题中,在任意时刻你都拥有一组区间。当且仅当满足 c<a<dc < a < d 或 c<b<dc < b < d 时,你才能从当前集合中的区间 (a, b)(a,\,b) 移动到当前集合中的另一区间 (c, d)(c,\,d)。此外,若存在一连串连续的移动,使得我们能从集合中的第 I1I_1 个区间出发最终到达集合中的第 I2I_2 个区间,则称集合中第 I1I_1 个区间到第 I2I_2 个区间之间存在一条路径。

你的程序需处理以下两类查询:

  1. 1 x y(其中 x<yx < y)—— 将新区间 (x, y)(x,\,y) 加入区间集合。保证新区间的长度严格大于所有之前加入的区间的长度。
  2. 2 a b(其中 a≠ba \neq b)—— 回答问题:是否存在从第 aa 个(下标从 1 开始计数)加入的区间到第 bb 个(下标从 1 开始计数)加入的区间的路径?

请回答所有查询。注意,初始时区间集合为空。

输入格式

The first line of the input contains integer n denoting the number of queries, (1 ≤ n ≤ 105). Each of the following lines contains a query as described above. All numbers in the input are integers and don't exceed 109 by their absolute value.

It's guaranteed that all queries are correct.

输入的第一行包含一个整数 nn,表示查询的数量(1 ≤ n ≤ 1051 ≤ n ≤ 10^5)。接下来的每一行包含一个如上所述的查询。输入中的所有数字均为整数,且其绝对值不超过 10910^9。

保证所有查询均合法。

输出格式

For each query of the second type print "YES" or "NO" on a separate line depending on the answer.

对于每个第二类查询,根据答案在单独一行输出“YES”或“NO”。

输入输出样例

  • 输入#1

    5
    1 1 5
    1 5 11
    2 1 2
    1 2 9
    2 1 2

    输出#1

    NO
    YES

输入解题思路,AI测评打分。不知道怎么写?

首页