题解：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，具体能不能进一步优化不清楚。

upd：

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