流星雨 Meteor Solution

· · 题解

这里是 流星雨 Meteor 的出题人题解。

这道题的部分分就不单独说了，因为正解会有部分能用上。

题意

给定一些直线，解析式形如 y_i=b_i-\dfrac{p_i}{q_i} x，询问 x=x_0 时，y_i\in[l,r]\cap\N 的直线 i 的权值和。其中 x_0,l,r,b_i\in[1,n]\cap \N。

分析

题目中保证了 v_i,t_i 互质，也就是直线斜率 \dfrac{p_i}{q_i} 是一个最简分数（这其实是为了方便造数据）。

询问首先可以差分成求前缀和，然后是一个显然的根号分治：

先考虑直线对询问做贡献：斜率分母是 q_i 时，y_i 是整数的位置 x_0 只有 O(\dfrac{n}{q_i}) 个。于是我们把 q_i>\sqrt{n} 的部分单独拉出来考虑。满足这个条件的直线都可以直接暴力算出 q_i 的倍数处的值。排一下序，和询问做双指针，就可以 O(n\sqrt{n}) 地得到这部分的答案。

以及，类似地，在 y 轴上也有这种限制：如果说斜率分子为 p_i，那么其最多过 \dfrac{b_i}{p_i} 轮就会跌出询问区间，于是这一部分也可以像上面一样，单独提出来做。这两部分由于值域不大，使用桶排即可做到时空 O(n\sqrt{n}+q)。

随后发现，其它类型的直线难以再应用上面的做法。

考虑某个斜率分母 q_i 剩下的直线对倍数处询问的贡献（也可以看成是把询问拆到因子处）。注意，由于我们上面的两步，现在有很重要的性质：p_i\leq \sqrt{n} 以及 q_i\leq \sqrt{n}。后者意味着我们的操作其实可以和值域相关了。（以及单独而不是均摊地与 Q 相关）。以下分析时间的时候，记 C_i 表示斜率分母为 i 处的直线条数，Q_i 表示倍数处的询问个数。

现在我们不用关心斜率分母，可以简单认为直线的斜率就是整数 -p_j。

在分母为 i(1\leq i\leq\sqrt{n}) 的处理：考虑把 B_i 条直线分为一块，这些直线的交点个数是 O(B_i^2) 的，把它们按横坐标排序，就可以维护它们的相对大小，然后和询问在横坐标上做双指针，询问的时候就可以二分出位置进行查询。维护相对大小的一步，就是在交点处交换其顺序；特别地，对于多线共交点的情况，是一个区间 reverse。操作总数和交点总数显然同阶。块内的操作复杂度是：O(B_i^2+Q_i\log B_i)。

诶？那交点排序怎么办呢？交点横坐标形如 x_0=\dfrac{\Delta{b}}{\Delta{k}}，而其中 \Delta{k}=p_i-p_j，是两个 \leq \sqrt{n} 的非负整数的差。那么，把交点化为带分数，其分数部分就只有至多 O(n) 种。纵坐标同理。于是仍然可以使用基数排序做到 O(n)（其实已经变成了桶排序）。以下进行复杂度分析：

对于这部分的处理：O(\dfrac{C_i}{B_i}\cdot (n+B_i^2)+Q_i\cdot \dfrac{C_i}{B_i}\log{B_i})。值得一提里面的 O(n)，你为了不让它成为瓶颈项，可能需要凑够很多数再做基排。而且即使凑不够，由于只会处理 1\leq i\leq \sqrt{n}，一共只有根号次，也不会成为瓶颈，可以认为和 O(B_i^2) 同阶，暂时略去。于是式子就是：O(C_iB_i + Q_i\cdot \dfrac{C_i}{B_i}\log{B_i})，取 B_i=\sqrt{Q_i\log{C_i}}（后面那个 \log 下面 B_i 和 C_i 没区别，所以写成 C_i） 就可以取到 O(C_i\sqrt{Q_i\log{C_i}})。

然后 Q_i\approx Q,\sum{C_i}=n，总复杂度就是 O(n\sqrt{Q\log{n}})。但是，实际做的时候，需要权衡各方面的常数（主要是基排常数有点大），所以块长取到 \sqrt{Q} 左右比较优秀。

实现相当优秀的快排做法或许可以通过。轻微卡常，轻喷。

Code Link.