自动搬运

查看原文

来自洛谷，原作者为

	JoshAlMan i人

搬运于2025-08-24 22:37:26，当前版本为作者最后更新于2022-03-30 17:49:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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

考虑这个题，考虑设定一个阈值 $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)$