题解：P8513 [Ynoi Easy Round 2021] TEST_136

· · 题解

题意：

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

线段完全在直线的下方就是两个点都在直线的下方，所以我们直接假装没有线段，问题转化为设给定线段下的点的数量为 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) 的，所以我们预处理前缀的答案，然后就做完了。