CF840D 题解

· · 题解

题解里面都是随机化，根号分治，主席树之类的。菜鸡表示完全想不到啊！！于是今天在外面游荡的时候胡了一个简单易懂的做法。

前情提要：本题解所用方法几乎是算法堆叠，毫无思维含量，所以不建议想练思维的巨佬们观看。

首先看到区间数字出现次数首先想到莫队。

那么我们很容易可以想到一个做法：用莫队维护数字出现次数，然后对于每个询问，从小到大枚举答案会是那个数，然后找到最小的满足条件的数。

然而这样做是 \operatorname{O}(n^2) 的，莫队的优势完全没有体现出来，考虑优化。

不难想到，我们可以二分这个最小的数。

假设当前二分到了 mid，那么我们需要快速知道所有 i 满足 1\le i\le mid 中有没有一个数的出现次数大于 \frac{r - l + 1} {k}，还要在莫队的指针移动时快速修改某一个位置上的值（更改其出现次数）。

用权值线段树或权值树状数组可以做到 \operatorname{O}(n\sqrt{n}\log n)。

这个做法有一个很重要的点（正解也需要这一点）：用线段树维护显然直接做就可以了，但是树状数组貌似不太能。

因为我们要求出的是前缀最大值，而莫队删除元素时可能会让最大值变小，这一点极其不好维护。

所以我们要避免删除元素。

那么莫队就要变为回滚莫队。（不会回滚莫队可以看这不要脸的宣传）

然而 \operatorname{O}(n\sqrt{n}\log n) 还是很难通过。（不管是线段树还是回滚莫队常数都很大），所以还要优化。

不难发现，我们对元素进行修改会进行 n\sqrt{n} 次，但查询信息只有 n\log n 次，所以不妨考虑从这一点入手。

所以我们需要一种修改复杂度极快，查询复杂度中等的数据结构来维护这些信息。

值域分块 可以很好的解决这个问题。

和树状数组一样，值域分块也不能像线段树一样快速合并信息所以我们也需要回滚莫队。

那么现在我们每次修改是 \operatorname{O}(1) 的了，但查询是 \operatorname{O}(\sqrt{n}) 的。

而我们需要查询 n\log n 次，所以时间复杂度不变。

假设我们要寻找的答案为 x，对值域分块后它在第 y 个块。

那么第 y 个块中的值出现次数的最大值一定大于 \frac{r - l + 1} {k}这不废话。所以我们可以从小往大暴力枚举块，然后找到最靠前的那个最大值大于 \frac{r - l + 1} {k} 的块。

这样就可以在 \operatorname{O}(\sqrt{n}) 的时间复杂度内确定答案所在块。

知道了答案在的块后，答案就出来了。

因为每个块的长度只有 \sqrt{n}，所以直接暴力枚举块中的每一个元素，找到最小的合法元素即可。

这样我们就把寻找答案的复杂度做到了 \operatorname{O}(\sqrt{n})，所以总时间复杂度 \operatorname{O}(n\sqrt{n}+m\sqrt{n})。

代码其实很好写，思路很顺，所以大概半个小时左右就能写完。

然后回滚莫队的常数貌似不是一般的大（也有可能是我写丑了），所以卡了很久的常。

正常代码（过不了，没卡常）

AC代码