众数杀手_杂项

众数杀手

感觉坑越开越多了。

最好的写法就是 set 找前驱后继。

rsrams

已收录于“lxl 根号数据结构”。

CF1446D1

给定序列 $a$，求最长的满足区间众数有至少两种的区间长度。

$n\le 2\times 10^5,a_i\le 100$。

有一个结论：全局众数一定是答案的众数之一，否则你可以扩展区间使得全局众数的出现次数追平区间众数。

于是我们首先知道一个答案是全局众数，然后利用 $a_i\le 100$，枚举另一种颜色，将全局众数视为 $1$，这种颜色视为 $-1$，其他颜色视为 $0$，则若另一种颜色被计入答案，则答案的一个必要条件是区间和为 $0$。

我们直接用前缀和计算区间和为 $0$ 的最长区间发现它对了，于是我们来证明不合法的区间一定不优：

• 区间和不为 $0$ 且区间合法当且仅当区间众数的出现次数大于全局众数，于是我们可以知道它肯定比答案劣，因为可以扩展它使得全局众数追平。

CF1446D2

$a_i\le n$。

做法一：无法故技重施了，我们考虑根号分治。

出现次数大于根号的只有根号个，我们可以跑一遍上面的做法，解决。

出现次数小于根号的我们考虑如何 $\Theta(\sqrt n)$ 解决，

考虑摒弃掉原来的想法，直接 $\Theta(n\sqrt n)$ 解决出现次数 $\le \sqrt n$ 的区间们。

枚举出现次数 $x$，从左往右跑双指针，右端点右移时如果让一个值超过了 $x$ 那么左端点右移，合法了就统计答案。

做法二：考虑小块的另一种处理方式：枚举小块中第一个出现的元素 $k$，设全局众数为 $m$，则我们只需要考虑 $k$ 前面 $\le \sqrt n$ 个 $m$（不能超过上一个小块元素），和后面 $\le \sqrt n$ 个 $m$（可以超过下一个小块元素），把这些有用的元素扔进一个新数组里跑。

处理一个小块元素的复杂度是 $\Theta(\sqrt n)$ 的，由于小块元素总个数不超过 $n$，复杂度 $\Theta(n\sqrt n)$。

做法三：拒绝根号分治，设 $x$ 的出现次数是 $c(x)$，如果我们能用 $\Theta(c(x)\log n)$ 的复杂度处理每个颜色，那我们就可以达到 $\Theta(n\log n)$。

考虑对该颜色求出所有“有用点”，具体来说从左到右枚举每个位置，每个位置匹配它后面的第一个 $m$ 并将其删掉，再从右往左枚举，每个位置匹配它前面的第一个 $m$ 并将其删掉，这就是所有可能出现在答案中的 $m$，使用 std:set。

而没出现在答案中的 $m$ 起到了分隔符的作用，你不能让答案跨过这些 $m$，不会处理的话就暴力跑几个 $m$ 扔进序列，这样前缀和就可以处理掉了。

一种简单的写法是直接对于每个元素找前面的一个 $m$ 后面的一个 $m$，然后将它们删掉，但这是假的（如果是绝对众数 $>\frac n 2$ 就可以前找一个后找一个），改成前面找一个后面找两个就对了。

总复杂度 $\Theta(n\log n)$。

做法四：考虑把做法三的 set 换成链表，你只需要支持对于每个元素查找他自己颜色的后继以及全局众数的后继即可，$\Theta(n)$。

P8349 [SDOI/SXOI2022] 整数序列

给定颜色序列和对应数组 $b_i$，$q$ 次询问两种颜色 $x,y$，试求出所有满足 $x,y$ 出现次数相同的区间中 $x,y$ 出现的位置的 $b_i$ 的和最大值。

$n\le 3\times 10^5,q\le 10^6,7\text{ seconds}$。

考虑根号分治，设 $B$ 为块长。

首先有一个 $\Theta(\text{len}_x+\text{len}_y)$ 解决 $(x,y)$ 的暴力：将两种颜色的位置提取出来，归并一下，相当于要跑上面那个题的区间和为 $0$ 的 $b_i$ 和最小的区间，对于每个 $a_i$ 前缀和记录前缀 $b_i$ 和最小值即可。

那么我们小块对小块和大块对大块就直接解决了。

复杂度证明：小块对小块不用说，$\Theta(B)$，大块对大块的话求出本质不同的询问们需要 $\sum_x\sum_y(\text{len}_x+\text{len}_y)$，拆开可得 $\le \Theta(\frac{n^2}{B})$。

那么考虑小块对大块：

考虑采用上面的做法，利用小块暴力匹配大块元素，扔进序列跑暴力，这里的匹配也可以采用链表，但需要维护每个元素前后的每个大块元素，较为麻烦，可以用 std::set 带 $\log$，更好写一点，复杂度是 $\Theta(B\log n)$。

总复杂度是 $\Theta(qB\log n+\frac{n^2}B)$，取 $B=\sqrt{\frac{n^2}{q\log n}}$ 可以平衡复杂度为 $\Theta(n\sqrt{q\log n})$。

P8330 [ZJOI2022] 众数