题解：P14136 【MX-X22-T7】「TPOI-4G」终焉

赛时降低了难度，所以并不需要快速 RMQ。

对颜色按出现次数和分块，使得每一块如果选了超过一种颜色，就必须总出现次数不超过 $\sqrt{\frac n{\log n}}$。

此时对于总出现次数不超过 $\sqrt{\frac n{\log n}}$ 的块，将出现的位置暴力取出，暴力算出每个区间的最大出现次数，然后对于每个给定的区间，在外面对 $l,r$ 分别排序，在分块的时候双指针，得出对应区间。

如果总出现次数超过了 $\sqrt{\frac n{\log n}}$，此时只有一种颜色，直接双指针求出该颜色的出现次数即可。

于是这样我们得出了每个给定的区间中，块内颜色的最大出现次数，此时做一个 $O(n)-O(1)$ RMQ 即可。

此时复杂度为 $O((n+m+q)\sqrt{n\log n})$。

然后对于查询的颜色散块，其出现次数总和不超过 $\sqrt{\frac n{\log n}}$，我们对所有询问的 $m$ 区间进行分治，分治时从 $mid$ 往两边做扫描线，将 $L_i,R_i$ 插到树状数组里，具体地，用树状数组记录 $L_i\le x$ 中最大的 $R_i$，然后对于询问枚举所有散块颜色，在散块内做双指针，在树状数组上面 $O(\log n)$ check，这里复杂度也是 $O(n+m+q)\sqrt{n\log n}$ 的。

于是我们得出了 $O((n+m+q)\sqrt{n\log n})$ 的可以通过的做法，空间 $O(n)$。

实际实现时 RMQ 仅仅进行 $\log$ 分块，而并没有处理查询端点同块的情况，因为时间来不及了。

块长调成 $0.87\sqrt n$ 即可通过，空间不到 64MiB。

对于颜色整块，直接对于 $L_i,R_i$ 这些区间做回滚莫队即可这样的空间复杂度会达到 $O(n\sqrt{n\log n})$。

这样至少有一个好处就是简单地去掉了快速 RMQ，具体能不能进一步优化不清楚。

发现这里也不需要开大空间，因为我们可以在回滚莫队时每求出 $\sqrt n$ 个答案就做取出得到答案的下标，暴力统计每个区间的最大值（硬要 ST 表也可以，不过我觉得还不如暴力统计快），再对询问的 $m$ 的左右端点进行双指针，这样又做到空间 $O(n)$ 了，但是如果忽略快速 RMQ 的话，这个算法要远远地比之前的算法难写。