题意
给定 \(N\) 个二维平面上的点 \((X_i, Y_i)\) 与 \(Q\) 组询问，每组询问给出一条直线 \(Y = A_iX + B_i\)，问有多少个点在直线上方（或者在直线上）。也就是询问有多少个 \((X_i, Y_i)\)，满足 \(Y_i \ge A_j \times X_i + B_j\)。
题解
首先这个式子是 \(A \times X + B \le Y\)，移项得 \(-A \times X + Y \ge B\)。那么，假设每组询问的 \(A\) 相等，那么把 \((X, Y)\) 按 \(-A \times X + Y\) 排序，然后二分答案即可。而对于 \(A\) 不同的情况，沿用刚才的方法，考虑维护这个排序后的序列（记为 \(B\)）。
这个序列显然不能在线维护，考虑离线。离线后对 \(Q\) 个询问按 \(A\) 从大到小排序，思考 \(A\) 变小后，序列会发生什么变化。也就是对于两个点对 \((X_i, Y_i), (X_j, Y_j)\) 且在序列 \(B\) 中有 \(i < j\)，原本存在关系 \(-A_1X_i + Y_i \le -A_1X_j + Y_j\)，移项得 \(-A_1(X_i - X_j) + (Y_i - Y_j) \le 0\)。在 \(A_1\) 变成 \(A_2\) ( \(A_2 \le A_1\) ) 后，如果 \(i\) 被放到 \(j\) 的后面，就存在 \(-A_2(X_i - X_j) + (Y_i - Y_j) \ge 0\)，孤立 \(A_2\) 之后得到 \(A_2 \le \frac{Y_i - Y_j}{X_i - X_j}\)，而 \(\frac{Y_i - Y_j}{X_i - X_j}\) 其实就是 \((X_i, Y_i)\) 与 \((X_j, Y_j)\) 两点所连直线的斜率。
然后这道题就可以做了。首先将询问按 \(A = +\infty\) 时的 \(-AX_i + Y_i\) 排序，其实就是将 \(X_i\) 按从大到小排序，\(X_i\) 相等时将 \(Y\) 从小到大。接着开一个小根堆存任意两点的斜率。一个一个询问往后扫，每次扫到一个新询问，看一下小根堆存的斜率里面有没有可以被更新顺序的。然后对 \(B_i\) 二分就行了。复杂度 \(O(Q \log N + N^2 \log N)\)，这题时限 10s 可以过。
code: