CF2143F.Increasing Xor

你收到了一个神奇的整数序列：$a_1, a_2, \ldots, a_n$。然而，这不是一个普通的序列，它可以以一种特定的方式自我修改！

经过仔细观察，你发现了它遵循的规则：

• 你可以反复选择任意两个下标 $1 \leq i \leq j \leq 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 \leq i \leq j \leq r$ 的下标）执行上述操作任意多次后，能否变为一个严格递增的序列。

$^{\text{∗}}\oplus$ 表示按位异或操作。

每组测试数据包含多个测试用例。第一行包含测试用例数 $t$（$1 \leq t \leq 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 < 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$ 能通过允许的操作变成严格递增序列，输出 YES；否则输出 NO。

你可以用任意大小写输出 YES 或 NO，例如 YES, yES, YeS 都是表示正解的有效输出。

在第一个测试用例中：

对于第一个询问，序列为 $[1]$，已经是递增的，无需修改。

对于第二个询问，序列为 $[1, 2]$，同样已经递增，无需操作。

对于第三个询问，序列为 $[1, 2, 2]$，它不是严格递增的，因此需要做操作。如果选择 $i = 1, j = 3$，执行 $a_3 \leftarrow a_3 \oplus a_1$，得到 $[1, 2, 3]$，已经严格递增，因此答案为 YES。

对于第四个询问，序列为 $[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$，区间变为 $[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]$，是严格递增序列。

由 ChatGPT 5 翻译