← 返回题目列表

Codeforces · 2096/F

F. 精彩的冒名顶替者

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

你是一位自豪的直播主播,名叫 Gigi Murin。今天,您将与编号为 $$$1$$$ 到 $$$n$$$ 的 $$$n$$$ 观众一起玩游戏。

在游戏中,每个玩家要么是队友,要么是冒名顶替者。你不知道每个观众的角色。

有 $$$m$$$ 语句,编号为 $$$1$$$ 到 $$$m$$$,它们是 是真是假。对于从 $$$1$$$ 到 $$$m$$$ 的每个 $$$i$$$,语句 $$$i$$$ 是以下两种类型之一:

  • $$$0\:a_i\:b_i$$$ ($$$1 \leq a_i \leq b_i \leq n$$$) — 观众中没有冒名顶替者 $$$a_i, a_i + 1, \ldots, b_i$$$;
  • $$$1\:a_i\:b_i$$$ ($$$1 \leq a_i \leq b_i \leq n$$$) — 有 至少 观众 $$$a_i、a_i + 1、\ldots、b_i$$$ 中的一名冒名顶替者。

回答以下形式的 $$$q$$$ 问题:

  • $$$l\:r$$$ ($$$1 \leq l \leq r \leq m$$$) - 语句 $$$l, l + 1, \ldots, r$$$ 是否可能是 全部正确?

请注意,这是 不保证 所有观众中至少有一名冒名顶替者,而且是 不保证 所有观众中至少有一名船员。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$、$$$m$$$ ($$$1 \leq n, m \leq 2 \cdot 10^5$$$) — 观看者数量和语句数量。

接下来的 $$$m$$$ 行的第 $$$i$$$ 包含三个整数 $$$x_i$$$, $$$a_i$$$, $$$b_i$$$ ($$$x_i \in \{0, 1\}$$$, $$$1 \leq a_i \leq b_i \leq n$$$) - 描述语句$$$我$$$。

下一行包含一个整数 $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — 问题数。

接下来的 $$$q$$$ 行包含两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \leq l \leq r \leq m$$$) — 描述一个问题。

保证所有测试用例的$$$n$$$总和不超过$$$2 \cdot 10^5$$$,所有测试用例的$$$m$$$总和不超过$$$2 \cdot 10^5$$$,所有测试用例的$$$q$$$总和不超过$$$2 \cdot 10^5$$$。

输出

对于每个问题,输出“是“如果所请求的陈述有可能全部为真。否则,输出“NO".

您可以在任何情况下输出答案(大写或小写)。例如,字符串“是", "是的", "是“,和”是”将被视为积极响应。

示例

输入
复制

4
4 3
1 1 3
1 2 4
0 2 3
1
1 3
5 2
0 1 5
1 1 5
3
1 1
2 2
1 2
1 2
0 1 1
1 1 1
2
1 1
2 2
7 9
1 2 2
1 4 5
0 5 6
1 2 2
1 1 1
0 4 7
0 3 7
0 2 7
0 6 6
5
1 5
2 6
3 7
4 8
5 9

输出
复制

YES
YES
YES
NO
YES
YES
YES
NO
YES
NO
YES

注意

在第一个测试用例中,有 $$$4$$$ 观看者和 $$$3$$$ 语句。声明如下:

  • 声明$$$1$$$:观众$$$1$$$、$$$2$$$和$$$3$$$中至少有一名冒名顶替者;
  • 声明$$$2$$$:观众$$$2$$$、$$$3$$$和$$$4$$$中至少有一名冒名顶替者;
  • 声明$$$3$$$:观众$$$2$$$和$$$3$$$中不存在冒名顶替者。

我们可以看到语句 $$$1$$$、$$$2$$$ 和 $$$3$$$ 都可能为真。例如,这是一种可能的情况:

  • 观看者 $$$1$$$ 是冒名顶替者;
  • 观看者 $$$2$$$ 是一名船员;
  • 观看者 $$$3$$$ 是一名船员;
  • 观看者 $$$4$$$ 是冒名顶替者。

在第二个测试用例中,有 $$$5$$$ 观看者和 $$$2$$$ 语句。声明如下:

  • 声明$$$1$$$:观众$$$1$$$、$$$2$$$、$$$3$$$、$$$4$$$和$$$5$$$中至少有一名冒名顶替者;
  • 声明$$$2$$$:观众$$$1$$$、$$$2$$$、$$$3$$$、$$$4$$$和$$$5$$$中不存在冒名顶替者。

我们可以看到,语句 $$$1$$$ 可能为真,语句 $$$2$$$ 也可能为真。然而,$$$1$$$ 和$$$2$$$ 不可能同时为真。