Description

给你一个长为 n 的序列 a,m 次询问,每次查询一个区间的众数的出现次数,强制在线。

Idea

分块。

预处理每两块之间的众数出现次数;用 $vector$ 存每种数值对应的所有元素下标;记录每个元素在 $vector$ 里的位置。

询问时,整块之间的答案已经预处理出来了,考虑 $2\sqrt n$ 个边角元素。

对于左边的边角元素 x,我们在相应的 vector 里找到下标为 $p_x+ans$ 的元素y,若 $y\leqslant r$,则说明该数值在范围内有至少 $ans+1$ 个数,暴力更新答案即可。

对于右边的边角元素,类似地处理即可。

Code