做题记录 25.10.1

· · 个人记录

\purple\odot CF1446D2 Frequency Problem (Hard Version)

设 a_{1\sim n} 的众数为 x，则最优情况下 x 是选择区间的众数，否则选择区间中存在一个数出现次数严格大于 x 出现次数，由于出现次数的连续性，一定能将其扩展直到该数字和 x 出现次数相同，一定更优

考虑根号分治，令阈值为 B，分别处理另一数字出现次数 >B 的和 \le B 的

出现次数 >B 的数显然不超过 \frac nB 个，暴力枚举该数字，该数字记为 +1，x 记为 -1，其他记为 0，则转化为求和为 0 的区间的最大长度，容易用桶做到 O(n)，这部分总时间复杂度 O(\frac{n^2}B)

另一数字出现次数 \le B 显然包含于两个数字出现次数都 \le B 的情况，枚举该出现次数 s，对于每个右端点，用桶双指针出最小的左端点，满足区间内所有数字出现次数 \le s，同时维护出现次数 =s 的数字数量，若数量 \ge 2 则跟新答案，这部分时间复杂度 O(Bn)

总时间复杂度 O(\frac{n^2}B+nB)，取 B=\sqrt n 则时间复杂度 O(n\sqrt n)

代码

参考