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$ 表示[按位异或操作](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)。

每组测试数据包含多个测试用例。第一行包含测试用例数 $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 翻译