Description

题目链接：P4168

给定一个长度为 $n$ 的序列，$m$ 次询问，每次询问输出区间众数，如果出现次数相同，输出编号小的。

强制在线。

$1\leq n\leq 4\times 10^4,1\leq m \leq 5\times 10^4,1\leq a_i\leq 10^9$

Solution

看到区间众数，自然而然就想到可以直接分块，时间复杂度 $O((N+M)\sqrt{N})$，空间复杂度 $O(N\sqrt{N})$，足矣通过此题，由于其他题解都写得很详细，这里就不再赘述。

那有没有更加优秀的算法呢？当然有，可以仿照P5048 [Ynoi2019 模拟赛] Yuno loves sqrt technology III的思路，预处理出 $[i,j]$ 块的众数出现次数，用 vector 按顺序存储每个数的所有元素出现位置，记录对应下标，每次询问的时候整块直接用预处理中的即可，散块个数最多为 $2\sqrt{N}$ 个，所以最多使答案增加 $2\sqrt{N}$，所以我们只需要扫一遍，判断这些数的出现个数是否能使答案加一即可。

总时间复杂度 $O((N+M)\sqrt{N})$，空间复杂度 $O(N)$，然而这种做法常数更小，所以跑得飞快，顺手卡一卡就拿到了最优解。

Code

普通分块：

第二种做法：