ABC344G 题解
给定平面上 \(n\) 个点和 \(q\) 条直线,问对于每条线,有多少点在它上方。
形式化的,对于直线 \(y=ax+b\) 统计有多少点 \((x,y)\) 满足 \(y\ge ax+b\),即 \(-ax+y\ge b\)。故我们可以将所有点按照 \(-ax+y\) 排序,从而利用二分简单的得出结果。
但是我们显然不可能暴力进行排序,本题重点在于优化。
key:对于每对点,它们的先后顺序只可能反转一次
证明:设点 \((x_1,y_1),(x_2,y_2)\)
- 若 \(x_1=x_2\),显然顺序只与 \(y_1,y_2\) 有关,不会改变
- 否则,设当前斜率为 \(A\),满足 \(-Ax_1+y_1<-Ax_2+y_2,x_1<x_2\)
\(\to A(x_2-x_1)<(y_2-y_1) \to A<\frac{y_2-y_1}{x_2-x_1}\)
如果反转,则说明 \(A<\frac{y_2-y_1}{x_2-x_1}<A'\)
显然,当 \(a\) 从小到大排序时,只会有一次反转
现在解法就变得显然了。
- 将所有直线按 \(a\) 从小到大排序,初始所有点按字典序排序
- 预处理每对点会在哪个 \(a\) 反转顺序,塞进优先队列
- 顺序处理每条直线,先反转所有应该反转的点,再二分答案
复杂度分析:
- \(O(q\log q + n\log n)\)
- \(O(n^2\log n)\)
- \(O(q\log n)\)
总复杂度为 \(O(q(\log q+\log n)+n^2\log n)\)
极限复杂度大概 \(6.6\times 10^8\),但时限 10s,所以能过。
tricks:
- 改写式子,分离变量
- 利用单调性,排序的更新可以与询问次数无关