CF2030F.Orangutan Approved Subarrays

假设你有一个数组 $b$。最初，你还有一个集合 $S$，其中包含 $b$ 的所有不同元素。如果数组 $b$ 能通过重复执行以下操作被清空，则称其为“orangutan-approved”：

• 每次操作，你可以选择下标 $l$ 和 $r$（$1 \leq l \leq r \leq |b|$），使得 $v = b_l = b_{l+1} = \ldots = b_r$，且 $v$ 在 $S$ 中。将 $v$ 从 $S$ 中移除，并同时移除所有 $l \leq i \leq r$ 的 $b_i$。然后，将 $b_{r+1}, b_{r+2}, \ldots$ 重新编号为 $b_l, b_{l+1}, \ldots$。

现在给定一个长度为 $n$ 的数组 $a$ 和 $q$ 个询问。

每个询问包含两个下标 $l$ 和 $r$（$1 \le l \le r \le n$），你需要判断子数组 $a_l, a_{l+1}, \ldots, a_r$ 是否为“orangutan-approved”。

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $q$（$1 \leq n,q \leq 2 \times 10^5$），分别表示数组 $a$ 的长度和询问数量。

接下来一行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq n$），表示数组 $a$ 的元素。

接下来的 $q$ 行，每行包含两个整数 $l$ 和 $r$，表示每个询问的子数组区间端点（$1 \leq l \leq r \leq n$）。

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

对于每个询问，如果从 $l$ 到 $r$ 的子数组是“orangutan-approved”，输出 "YES"（不带引号），否则输出 "NO"（不带引号）。

你可以用任意大小写输出 "YES" 和 "NO"（例如 "yES"、"yes"、"Yes" 都会被视为肯定回答）。

在第一个测试用例的第一个询问中，答案是 YES。

• 初始时，$S=\{1,2\}$，$b=[1,2,2,1]$。
• 选择 $l=2$ 和 $r=3$。由于 $b_2=b_3=2$ 且 $2$ 在 $S$ 中，我们可以将 $b_2$ 和 $b_3$ 从数组中删除，同时将 $2$ 从 $S$ 中删除。此时 $S$ 变为 $\{1\}$，数组变为 $[1,1]$。
• 选择 $l=1$ 和 $r=2$。由于 $b_1=b_2=1$ 且 $1$ 在 $S$ 中，我们可以将 $b_1$ 和 $b_2$ 从数组中删除，同时将 $1$ 从 $S$ 中删除。此时 $S$ 变为 $\{\}$，数组变为空。
• 由于数组已被清空，我们可以说原数组是“orangutan-approved”。

在第二个测试用例的第一个询问中，答案是 NO，因为可以证明子数组 $[2,1,2,1]$ 无法通过任何有效操作序列被清空。

由 ChatGPT 4.1 翻译