CF2149G.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$。

在第二个测试用例中，数组 $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$。

由 ChatGPT 5 翻译