题解 P8330【[ZJOI2022] 众数】

· · 题解

P8330 [ZJOI2022] 众数 解题报告：

更好的阅读体验

题意

给定一个长度为 n 的序列，你能对它进行一次区间加，最大化众数出现次数。

## 分析 ZJOI T2，传统签到题！场外选手来口胡一下。 显然答案的形态就是 aaabbbaaa，考虑对颜色出现次数根号分治： - a/b 存在一个是大颜色：枚举每一个大颜色，扫一遍序列，对每种颜色维护一个极长的 aaabbb 段以及一个 bbbaaa 段即可。 - a/b 均为小颜色：枚举处于外面的颜色，那么问题转化为 $O(n\sqrt n)$ 次区间众数。但此时众数大小不超过根号，我们将询问有序地挂在右端点，枚举众数出现次数，移动右端点并维护符合条件最靠后的左端点，弹符合要求的询问就好了。 这样就做到了 $O(n\sqrt n)$。 ## 代码 咕了。