题解[Ynoi2006]rsrams

· · 题解

非常有幸在某谷上成为了跑得最快的一个至少在笔者写题解时是如此的，所以来水一篇题解。

顺便批判一下某个为了让题目价值最大化的人，居然把公开了的题隐藏了又拿出来卖(详见某谷评论区)，笔者不幸成为了受害者。(；´д｀)ゞ

好的，那让我们开始讲讲这道题吧。

首先让我们想想颜色数量比较少，譬如颜色数为 2 的情况，有什么比较好的解决方法。

由于它要求的是区间段内一种颜色的出现次数严格大于其它颜色的数量，我们不妨将该种颜色的值看作 1，其它颜色的值看作 -1，那么我们的要求就转化为了区间之和要大于0。我们可以考虑用哪个前缀和的差分来维护区间，这样我们就相当于要对每个前缀和统计它前面有多少个比它小，经典的二维偏序问题。

那许多颜色时，如果我们再一个颜色一个颜色的这么做不就 O\left(n^2\right) 了吗？这不 T 飞。

没事，我们观察到对于每个颜色真正有用的区间是非常少的，经常会出现很长一段区间一个该颜色的点都没有的情况。

我们可以对于该颜色可能成为绝对众数（也就是它的出现次数超过一半），找到它的可能区间，只考虑这个区间内众数的计算。对于这个可能的区间，我们可以去找它的最左左端点与最右右端点，把它们之间看作这种颜色的一个可能区间。

下面给出一种比较简单的找法，从左到右枚举每个该颜色的位置，选中它左边第一个尚未被选择到的不是该颜色的位置。再从右到左枚举每个该颜色的位置，选择它右边第一个尚未被选择的不是该颜色的位置。

显然，所有选择位置与该颜色的位置构成的连通块就是一个可能的区间。你再选连通块外的任意一个点，必然不可能构成包含该连通块中点的总和为正的区间，也就不会对答案产生任何贡献。

好的，这样我们就能非常简单地求出我们的可能区间了。可以发现，这个可能区间有一些非常好的性质：

首先，只有当询问区间与可能区间相交时，可能区间才会对答案产生贡献。考虑询问区间与可能区间相交的三种情况。

其中，对于第一种情况，显然就是个二维数点问题。我们可以先将每个可能区间的总贡献值算出来，然后加在点上。排序后用一个树状数组就可以 O\left(n\log n\right) 地维护。

对于第二种情况，我们可以询问区间肯定包含可能区间的某个前后缀，我们不妨考虑把这个前后缀的答案预处理出来，再在询问区间的左右端点上，枚举处于这种情况的可能区间有哪些，将前后缀的贡献加入答案，显然，这部分时间复杂度是 O\left(n\log n\right)。

诶，单纯预处理一个全局或者前后缀的逆序对数量是 O\left(n\log n\right) 的二维数点吗？显是可以优化的，毕竟我们这里的值的变化时连续的，也感谢 \rm Cirno\_9 为我点明了这个方法。

可以发现，我们值的变化都是形如 k=1/-1 的直线。大概是这个样子

我们可以考虑记录 cnt_i 表示前缀值和为 i 的前缀数量，再记录一个 now 表示比右端点小的前缀的数量。

假设我们现在右端点处值为 x，如果它右移一步，增大 1，也就是说现在比它小的点前缀数量增加了 cnt_x，我们就将 now 加上 cnt_x。再将现在的 now 计入总的答案。

这样，我们就可以做到 O\left(n\right) 地维护全局及前后缀的答案了。

我们现在再来考虑我们的第三种情况，显然，这就相当于查询我们的询问区间在全局区间中对应的区间逆序对数量，这不是可以考虑莫队吗？

我们可以将所有的这样的询问离线下来，对于每个可能区间单独做莫队，依旧用我们上面的方法实时维护答案，也就没必要二次离线了。

每个长度为 n' 的，有 m' 个询问的区间的时间复杂度为 O\left(n'\sqrt{m'}\right)，第三类的总时间复杂度为 O\left(n\sqrt{m}\right)。

最后只需要把每一类对该询问区间的贡献加在一起，就可以得到该询问区间的总答案了。

总时间复杂度为 O\left(n\sqrt{m}+(m+n)\log n\right)。

code