← 返回题目列表

Codeforces · 2143/F

F. 增加异或

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

你被赋予了一个神奇的整数序列:$$$a_1, a_2, \ldots, a_n$$$。然而,这不是普通的序列——它可以以特定的方式修改自己!

仔细观察后,你发现了它的规律:

  • 反复选择两个索引 $$$1 \le i \le j \le n$$$。
  • 然后,索引 $$$j$$$ 处的值更新为: $$$a_j \leftarrow a_j \oplus a_i$$$.$$$^{\text{*}}$$$

由于害怕严格递增的序列,你开始问自己问题:

您收到 $$$q$$$ 查询。每个查询由两个整数 $$$l$$$ 和 $$$r$$$ 组成,并且您必须确定子数组 $$$a_l, a_{l+1}, \ldots, a_r$$$ 是否可以通过仅在 $$$l$$$ 到 $$$r$$$ 范围内应用任意数量的所描述的操作来转换为严格递增序列,即, 仅使用索引 $$$l \le i \le j \le r$$$.

$$$^{\text{*}}$$$$$$\oplus$$$ 表示按位异或运算。

输入

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

第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \leq n, q \leq 2 \cdot 10^5$$$) - 序列的长度和查询的数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \lt 2^{20}$$$) — 序列的内容。

接下来的 $$$q$$$ 行包含两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \leq l \leq r \leq n$$$),表示一个查询。对于每个查询,您必须确定是否可以使用允许的操作将子数组 $$$a_l, a_{l+1}, \ldots, a_r$$$ 转换为严格递增序列。

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

输出

对于每个查询,输出 是 如果子数组 $$$a_l, a_{l+1}, \ldots, a_r$$$ 可以使用允许的操作转换为严格递增序列;否则,输出 NO.

您可以打印以下每个字母 是 or NO 无论如何。例如, 是, 是, 是的 将全部被识别为肯定答案。

示例

输入
复制

2
4 4
1 2 2 1
1 1
1 2
1 3
1 4
8 6
5 1 1 2 3 2 1 3
1 8
2 2
2 3
2 6
4 8
5 8

输出
复制

YES
YES
YES
YES
NO
YES
YES
NO
NO
YES

注意

在第一个测试用例中:

对于第一个查询,序列是$$$[1]$$$,它是递增的,因此不需要更改。

对于第二个查询,序列是$$$[1, 2]$$$,也是递增的,无需更改。

对于第三个查询,序列是 $$$[1, 2, 2]$$$,这不是 严格 不断增加,因此我们必须进行一些操作。如果我们应用 $$$i = 1, j = 3$$$ 则 $$$a_3 \leftarrow a_3 \o​​plus a_1$$$。该序列变为 $$$[1, 2, 3]$$$,现在严格递增。因此,答案是肯定的。

对于第四个查询,序列为 $$$[1, 2, 2, 1]$$$。我们可以执行以下操作:

  1. $$$a_2 \leftarrow a_2 \oplus a_2 (i = 2, j = 2)$$$。序列变为 $$$[1, 0, 2, 1]$$$。
  2. $$$a_4 \leftarrow a_4 \oplus a_3 (i = 3, j = 4)$$$。序列变为 $$$[1, 0, 2, 3]$$$。
  3. $$$a_2 \leftarrow a_2 \oplus a_1 (i = 1, j = 2)$$$。序列变为 $$$[1, 1, 2, 3]$$$。
  4. $$$a_1 \leftarrow a_1 \oplus a_1 (i = 1, j = 1)$$$。该序列变为严格递增的 $$$[0, 1, 2, 3]$$$。

在第二个测试用例中:

对于第一个查询,不可能使整个序列严格递增。

对于第二个查询,序列是$$$[1]$$$,它已经是严格递增的,因此不需要更改。

在第三个查询中,序列为 $$$[1, 1]$$$。我们可以通过选择 $$$i = j = 2$$$ (指原始序列中的索引)并执行操作 $$$a_2 \leftarrow a_2 \oplus a_2$$$ 来使其严格递增。这设置了 $$$a_2 = 0$$$,导致索引 2 到 3 的子数组变成 $$$[0, 1]$$$,这是严格递增的。

对于最终的查询,我们可以按此顺序执行以下操作:

  1. $$$a_6 \leftarrow a_6 \oplus a_5$$$
  2. $$$a_7 \leftarrow a_7 \oplus a_5$$$
  3. $$$a_5 \leftarrow a_5 \oplus a_5$$$

经过这些操作,索引 5 到 8 的子数组变为 $$$[0, 1, 2, 3]$$$,这是严格递增的。