← 返回题目列表

Codeforces · 2149/G

G. 布拉多 3

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

在蓝锁的残酷世界里, 布拉多 3 是一个被选中推翻卫冕冠军并带领日本 U-20 队走向辉煌的三人组。 纱江伊东 已经锁定了第一名参赛者的位置;剩下的两个名额将在艰难的B面选拔中争夺。

为了测试候选人的战略能力,Buratsuta提出了以下挑战:

给您一个名为“性能记录”的 $$$n$$$ 整数数组和 $$$q$$$ 查询。每个查询指定一个子数组$$$[l, r]$$$。在此子数组中,查找出现的所有记录值 严格更多 比 $$$\lfloor\tfrac{r - l + 1}{3}\rfloor$$$ 倍。

输入

每个测试由多个测试用例组成。

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

下面介绍测试用例。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ $$$(1 \le n, q \le 2\cdot10^5)$$$ — 记录数和查询数。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le 10^9)$$$ — 性能记录。

以下 $$$q$$$ 行中的每一行都包含两个整数 $$$l$$$ 和 $$$r$$$ $$$(1 \le l \le r \le n)$$$ — 查询的边界。

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

输出

对于每个查询,在一行中输出出现的所有记录值(按排序顺序) 严格更多 比 $$$[l, r]$$$ 段中的 $$$\lfloor\tfrac{r - l + 1}{3}\rfloor$$$ 倍。如果没有这样的值,则输出$$$-1$$$。

示例

输入
复制

5
1 1
5
1 1
4 2
1 1 2 3
1 4
2 3
6 3
7 7 7 8 8 9
1 6
2 5
4 6
8 2
4 4 4 5 5 5 6 6
1 8
3 6
10 5
1 2 3 3 3 4 4 4 4 5
1 10
1 5
4 9
6 9
7 10

输出
复制

5
1
1 2
7
7 8
8
4 5
5
4
3
4
4
4

注意

在第二个测试用例中,数组为 $$$a=[1,1,2,3]$$$ 并且有两个查询:

  • 查询$$$(l,r)=(1,4)$$$:线段长度$$$len=r-l+1=4$$$,阈值$$$\bigl\lfloor \frac{len}{3}\bigr\rfloor+1 = 2$$$。数字出现次数:$$$1\!\to\!2$$$、$$$2\!\to\!1$$$、$$$3\!\to\!1$$$。只有数字 $$$1$$$ 至少出现 $$$2$$$ 次,所以答案是:$$$1$$$。
  • 查询$$$(l,r)=(2,3)$$$:段长度$$$len=2$$$,阈值$$$\bigl\lfloor \frac{len}{3}\bigr\rfloor+1 = 1$$$。数字 $$$1$$$ 和 $$$2$$$ 各出现一次,所以答案是:$$$1 \; 2$$$。

在第四个测试用例中,数组为 $$$a=[4,4,4,5,5,5,6,6]$$$ 并且有两个查询:

  • 查询$$$(l,r)=(1,8)$$$:段长度$$$len = 8$$$,阈值$$$\bigl\lfloor \dfrac{len}{3} \bigr\rfloor + 1 = 3$$$。

    数字出现次数:$$$4 \!\to\! 3$$$, $$$5 \!\到\! 3$$$, $$$6 \!\到\! 2$$$。只有数字 $$$4$$$ 和 $$$5$$$ 至少出现 $$$3$$$ 次,所以答案是:$$$4 \; 5$$$。

  • 查询$$$(l,r)=(3,6)$$$:段长度$$$len = 4$$$,阈值$$$\bigl\lfloor \dfrac{len}{3} \bigr\rfloor + 1 = 2$$$。

    数字出现次数:$$$4 \!\to\! 1$$$, $$$5 \!\到\! 3$$$。只有数字 $$$5$$$ 至少出现 $$$2$$$ 次,所以答案是:$$$5$$$。