这题用根号分治是不是能做

金珂拉 @ 2022-09-26 18:52:36

by ppip @ 2022-09-26 19:06:55

具体流程？

by 金珂拉 @ 2022-09-26 19:20:46

@ppip emm，打了打发现做不了

在处理小颜色的时候会发生只能求出数量无法求出众数的情况。

by ppip @ 2022-09-26 19:21:58

小颜色是啥

by _zexal_ @ 2022-09-26 19:22:09

@金珂拉 可以用来练练分块，只要复杂度小于 O(n\sqrt n) 就能过啦。

by ppip @ 2022-09-26 19:22:27

如果指区间长度 \le\sqrt{n} 有任何困难吗

by 金珂拉 @ 2022-09-26 19:25:16

@ppip 在整个区间里个数小于 \sqrt n 的数。

就是今年ZJOI D1T2的思路啊

by 金珂拉 @ 2022-09-26 19:26:02

@zhong114514 主要是根号分治想法是错的）我想练根号分治的来着，发现这题貌似做不了根号分治（

by 金珂拉 @ 2022-09-26 19:27:31

@ppip 如果不需要求最小众数那思路就是简单枚举众数的个数，然后预处理 pre_k 的前缀最大值和 l 比一下就行…… 但是这题这么搞根号分治就做不了了）