推广一种值域分块的静态区间众数做法。

虽然比常规做法劣（劣在不能优化空间复杂度），但是感觉这种思考方法还是有意义的。

首先把所有的数按其值排序，相同的数按不同的数算，记下排好序的数在原序列中的位置，再单独拿出来每个块中的数按原序列中位置排个序，然后按块长 $= B$ 分块。

这样由于块里面只有 $B$ 个数，因此对于一个块来说本质不同的询问只有 $O(B^2)$ 种。

是可以做到 $O(1)$ 找到某个特定区间内在一个值域块中的众数的，这一步可以平凡地预处理三个数组：

• $last(pos, block\_id), next(pos, block\_id)$ 表示原序列中 $pos$ 位置前/后第一个在第 $block\_id$ 个值域块中的位置是该值域块中的第几个数，两个数组都是 $O(n^2/B)$ 空间的，显然可以直接从左到右再从右到左扫两遍直接平凡地预处理出来。
• $ans(block\_id, l, r)$ 表示第 $block\_id$ 个值域块中，第 $l$ 个位置到第 $r$ 个位置的众数，这个也是可以直接暴力预处理的，时空复杂度均为 $O(nB)$。

回忆序列分块的区间众数，大家知道它是不支持两个区间的信息合并的，但是这里不同，当不考虑值域块边界的数的时候，每个值域块中的数一定是不相交的，所以可以合并，合并的复杂度为 $O(n/B)$。

接下来，值域块边界的数也可能成为答案，但是由于这样的数只有 $O(B)$ 个，同样可以暴力预处理前缀和，然后直接算次数。

当 $B = \sqrt n$ 时可以做到 $O(n\sqrt n)$ 的时空复杂度。

代码比起常规序列分块的做法难写不少，因此我也没写代码，但是感觉这个值域分块以使得信息支持合并的想法很不错，值得思考一下。