题解 P5048【[Ynoi2019 模拟赛] Yuno loves sqrt technology III】

· · 题解

[$\text{Link}$](https://www.luogu.com.cn/problem/P5048) ## 题意 区间众数出现次数，**强制在线**。 $n,q\le 5\times 10^5$。 ## 思路 考虑将序列按块长 $B$ 分块。 首先，如果 $l,r$ 在一个块内，可以直接暴力。 对于整块部分，我们预处理 $f_{L,R}$ 代表第 $L$ 个块与第 $R$ 个块内的众数的出现次数。这是平凡的。 考虑逐个加入散块部分的数，维护 $ans$ 表示当前众数出现次数，如果新加入的 $x$ 比现在的答案优，则它至少在 $[l,r]$ 内出现 $ans+1$ 次。 那么我们不妨枚举散块内的数，依次判断这个数在区间内是否出现了 $ans+1$ 次或以上，如是则将 $ans$ 加一直到出现次数不及 $ans+1$。 求一个数在区间中的出现次数看似困难，以左散块部分为例（右散块部分同理），其实我们求的是位置为 $p$ 的数在 $[p+1,r]$ 这段区间内出现次数是否达到 $c$ 次。我们使用 `vector` 存下每种数出现的所有下标，并求出 $t_i$ 数组表示 $a_i$ 这个数是第几次出现（即在 $i$ 在相应 `vector` 中的下标，注意加减一），那么上述问题即为 $a_p$ 对应 `vector` 的第 $t_p+c-1$ 个数是否 $\le r$。 分析复杂度，$n,q$ 同阶，时间复杂度为 $O(\dfrac{n^2}B+nB)$，令 $B=\Theta(\sqrt n)$，时间复杂度取到 $O(n\sqrt n)$，空间复杂度线性。 代码实现不难，我三年前的码风十分难接受，如果实在有需要，可以在此[云剪切版](https://www.luogu.com.cn/paste/lfgmn9bs)查看。