← 返回题目列表

Codeforces · 1883/D

D. 恋爱了

中文机器翻译题面 查看原题

最初,您有一个空的多重段集。您需要处理两种类型的 $$$q$$$ 操作:

- $$$+$$$ $$$l$$$ $$$r$$$ — 将段 $$$(l, r)$$$ 添加到多重集,
- $$$-$$$ $$$l$$$ $$$r$$$ — 从多重集中删除一个片段 $$$(l, r)$$$。保证该段存在于多重集中。

每次操作后,您需要确定多重集中是否存在一对不相交的线段。如果不存在满足 $$$l \leq x \leq r$$$ 和 $$$a \leq x \leq b$$$ 的点 $$$x$$$,则一对线段 $$$(l, r)$$$ 和 $$$(a, b)$$$ 不会相交。

输入

每个测试用例的第一行包含一个整数 $$$q$$$ ($$$1 \leq q \leq 10^5$$$) — 操作数。

接下来的 $$$q$$$ 行描述了两种类型的操作。如果是加法运算,则以$$$+$$$ $$$l$$$ $$$r$$$ 的格式给出。如果是删除操作,则以 $$$-$$$ $$$l$$$ $$$r$$$ ($$$1 \leq l \leq r \leq 10^9$$$) 的形式给出。

输出

每次操作后,如果多重集中存在一对不相交的线段,则打印“YES”,否则打印“NO”。

您可以以任何大小写形式打印答案(大写或小写)。例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定答案。

示例

输入 #1

12
+ 1 2
+ 3 4
+ 2 3
+ 2 2
+ 3 4
- 3 4
- 3 4
- 1 2
+ 3 4
- 2 2
- 2 3
- 3 4

输出 #1

NO
YES
YES
YES
YES
YES
NO
NO
YES
NO
NO
NO

注意

示例中,在第二次、第三次、第四次和第五次操作之后,存在一对不相交的线段 $$$(1, 2)$$$ 和 $$$(3, 4)$$$。

然后我们正好删除一个段 $$$(3, 4)$$$,到那时我们就有了两个段。所以,这个操作之后的答案也是存在的。