自动搬运

查看原文

来自洛谷，原作者为

	Butterfly_qwq 最后在线时间：2025年8月24日22时0分

搬运于2025-08-24 22:39:44，当前版本为作者最后更新于2025-08-12 08:02:55，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意：

有若干个任何颜色的点，若两个点颜色相同则这两个点之间有一条以这两个点为端点的线段，每次询问给你一条直线，问有多少个线段完全在直线的下方。

线段完全在直线的下方就是两个点都在直线的下方，所以我们直接假装没有线段，问题转化为设给定线段下的点的数量为 $c_i$，求 $\frac{c_i^2+c_i}{2}$。

那么就是要求两个东西，一次方和二次方。

我们注意到线段下的点十分甚至九分的不好做，所以把给定的直线变成点，点变成直线，这个是一个很经典的转换。

先看一次方。注意到对于一次方，每条直线（即原先的点，以后不做说明，均为变换后）颜色并没有用。

这个东西应该叫 UOJ NOI Round4 Day2 T2 己酸集合。

首先我们有一个 $O((n^2+q)\log n)$ 的做法：把 $n^2$ 个交点都求出来然后排序一遍就能找出每一个点线段的顺序，查询的时候对 $x$ 二分找到顺序再对 $y$ 二分就可以得到答案了。

这并过不去，问题在于 $n$ 和 $q$ 量级差太多了，那么我们考虑根号平衡，对每 $B$ 个线段做这个东西做 $\frac{n}{B}$ 次。

那么时间复杂度为 $O(\frac{n}{B}(B^2+q)\log n)$，取 $B=\sqrt{q}$ 就可以得到时间复杂度为 $O(n\sqrt{q}\log n)$。

然后一次方就做完了。

二次方的话，你直接对每一种颜色做一个己酸集合不就做完了吗，然而你发现假了，因为如果每种点的颜色互不相同就炸了，分块有一个上取整。

所以我们只能对直线数量 $\ge\sqrt{q}$ 的颜色做这个东西。

如果直线数量的颜色 $<\sqrt{q}$，考虑对于每一种颜色，加到集合里，直到集合里 $\ge\sqrt{q}$ 再做一次暴力就行了。

注意到由于每次加的都是小集合，所以每次集合里的大小是 $O(\sqrt{q})$。

但是多个颜色可能并不好很好的处理，所以我们要对算法改进。

考虑到每个交点只会交换，所以前缀的改变量是 $O(1)$ 的，所以我们预处理前缀的答案，然后就做完了。