P8261 [CTS2022] 袜子 题解

· · 题解

没利用到随机性质，哈哈。

首先询问半平面点个数是可做的，一种做法 是分块后极角排序双指针，询问二分。

考虑这个题，考虑设定一个阈值 B，颜色出现次数 >B 的之间套上面那个做法，小的考虑，每次把颜色相同的放到一组里，只需要动态维护一下这个顺序下，每个点有多少颜色相同的在它前面，并且快速求前缀和，这个可以树状数组，并且和排序同瓶颈。

既然出现次数都 \le B 了，那么我们分组可以把每块固定在 [B, 2B) 范围内，这样每组都是 O(B) 的了。

总复杂度 O(B^2\frac{n}{B} \log { B^2} + q \frac{n}{B} \log {B^2})，取 B = \sqrt{q} 最优，为 O(n\sqrt{q}\log q)