← 返回题目列表

Codeforces · 2030/F

F. 猩猩批准的子阵列

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

假设你有一个数组$$$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$$$ 中。从$$$S$$$中删除$$$v$$$,并同时删除所有$$$b_i$$$,使得$$$l \leq i \leq r$$$。然后,相应地将元素 $$$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$$$ 是否是猩猩认可的。

输入

第一行包含 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含整数 $$$n$$$ 和 $$$q$$$ ($$$1 \leq n,q \leq 2 \cdot 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 \cdot 10^5$$$。

输出

对于每个查询,如果从 $$$l$$$ 到 $$$r$$$ 的子数组经过猩猩批准,则输出“YES”(不带引号),否则输出“NO”(不带引号)。

在任何情况下都可以输出“YES”和“NO”(例如,字符串“yES”、“yes”和“Yes”将被识别为肯定响应)。

示例

输入 #1

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

输出 #1

YES
YES
NO
YES
YES
YES
NO
YES
YES

注意

在第一个测试用例的第一个查询中,答案是“是”。

- 最初,$$$S=\{1,2\}$$$ 和 $$$b=[1,2,2,1]$$$
- 选择$$$l=2$$$ 和$$$r=3$$$。由于$$$b_2=b_3=2$$$在$$$S$$$中,我们可以从数组中删除$$$b_2$$$和$$$b_3$$$,并从$$$S$$$中删除$$$2$$$。集合 $$$S$$$ 变为 $$$\{1\}$$$,数组变为 $$$[1,1]$$$。
- 选择$$$l=1$$$ 和$$$r=2$$$。由于$$$b_1=b_2=1$$$在$$$S$$$中,我们可以从数组中删除$$$b_1$$$和$$$b_2$$$,并从$$$S$$$中删除$$$1$$$。集合 $$$S$$$ 变为 $$$\{\}$$$,数组变为 $$$[]$$$。
- 由于数组现在为空,我们可以说原始数组是猩猩批准的。

在第二个测试用例的第一个查询中,答案是否定的,因为可以证明子数组 $$$[2,1,2,1]$$$ 不能通过任何有效操作序列变空。