Buratsuta 3

题目描述

在残酷的 Blue Lock 世界中，Buratsuta 3 是被选中推翻现任冠军并带领日本 U-20 队走向荣耀的三人组合。Sae Itoshi 已经锁定了首席席位，剩余两个名额将在激烈的 Side-B 选拔中角逐。

为了考察候选人的战略能力，Buratsuta 给出了如下挑战：

给定一个长度为 $n$ 的整数数组“表现记录”以及 $q$ 个查询。每个查询指定了一个子数组 $[l, r]$ 。在该子数组中，找出所有出现次数严格大于 $\lfloor\frac{r - l + 1}{3}\rfloor$ 的记录值。

每组测试数据包含若干个测试用例。

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

以下内容描述每个测试用例。

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

对于每个查询，输出一行，包含在区间 $[l, r]$ 内出现次数严格大于 $\lfloor\frac{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

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

查询 $(l,r)=(1,4)$ ：区间长度 $len=r-l+1=4$ ，阈值 $\left\lfloor \frac{len}{3}\right\rfloor+1 = 2$ 。数字出现次数： $1\to2$ ， $2\to1$ ， $3\to1$ 。只有数字 $1$ 出现次数不少于 $2$ ，因此答案为 $1$ 。
查询 $(l,r)=(2,3)$ ：区间长度 $len=2$ ，阈值 $\left\lfloor \frac{len}{3}\right\rfloor+1 = 1$ 。数字 $1$ 和 $2$ 都出现了一次，因此答案为 $1\ 2$ 。

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

查询 $(l,r)=(1,8)$ ：区间长度 $len=8$ ，阈值 $\left\lfloor \frac{len}{3}\right\rfloor+1=3$ 。数字出现次数： $4\to3$ ， $5\to3$ ， $6\to2$ 。只有 $4$ 和 $5$ 出现次数不少于 $3$ ，因此答案为 $4\ 5$ 。
查询 $(l,r)=(3,6)$ ：区间长度 $len=4$ ，阈值 $\left\lfloor \frac{len}{3}\right\rfloor+1 = 2$ 。数字出现次数： $4\to1$ ， $5\to3$ 。只有 $5$ 出现次数不少于 $2$ ，因此答案为 $5$ 。

见题面。