给你一个长度为 $N$ 的数列 $num\{\}$ 和常数 $K$ , 一共 $M$ 次询问 , 每次询问包含一个区间 $l,r$ : (其中 $\text A(num_i)$ 为 $\sum\limits^r_{j=l} [num_j=num_i]$)

$$\max\limits_{l \leq i,j \leq r , \text A(num_i) \ge \text A(num_j) , \text A(num_i)-\text A(num_j) \leq k} \text A(num_i)$$

考虑莫队 , 进行回滚 , 这样子 $\text A(num_i)$ 就只会加不会减。

考虑每一次加都会在另一导向的桶中消除 $\text A(num_i)-1$ 的贡献 , 一个一个的加上 $\text A(num_i)$ 的贡献 , 考虑到这个贡献只对 $\text A(num_i)-1$ 的贡献有影响 。 但是我们不需要判断判断 $\text A(num_i)-1$ 的贡献是否磨灭 , 因为答案只可能是 $\text{now} ans$ 或者 $\text A(num_i)$ , 如果变成了 $\text A(num_i)$ 那么就不可能再变成 $\text{now} ans$ 了 , 所以就算是 $\text A(num_i)-1$ 也没有关系了。

这就需要我们把莫队的询问拆出来以后按照 $num_i$ 排序 , 要基数排序 , 因为回滚的常数很大。

$O(NM^{\frac{1}{2}})$