自动搬运

查看原文

来自洛谷，原作者为

	CYJian 今日はこっちの地方はどしゃぶりの晴天でした，昨日もずっと暇で一日満喫してました

搬运于2025-08-24 22:04:42，当前版本为作者最后更新于2018-09-01 21:19:08，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

首先需要知道一个常识:两条直线相交后,这两条直线在交点右侧的大小关系就会改变.如果有多条直线计算排名,则会导致两条直线交换排名,且这两条直线在交点附近排名必然相邻.所以可以直接把这两条直线的一条排名+1,一条排名-1,这样就可以稳定过了..

这个应该算是常识吧..或者说很显然

然后对于这道题,我们就只要算出所有直线两两之间的交点并且按照$x$排好序,然后把询问离线排序处理.

先将所有点按照最靠左的询问排好序,然后每经过一个交点就把直线的排名更新一下.处理询问的时候就直接用排名为$k$的直线更新就好了.

代码

Updata (2018.9.21):

感谢 @打脸不疼 提供的Hack数据..

(但是数据中并没有加入这一组数据,请求管理员加入)

现在标算已修改,这里是代码