人类智慧

Undead2008 · 2025-03-21 21:38:08 · 题解

KDT 常数大！非常慢！跑 7 秒跑不过！

我们充分发扬人类智慧：

将询问的直线全离线下来，然后按照斜率从小到大排序，再挨个用 KDT 查。

根据乱搞直觉，在排序后，短时间内访问的内存一定有很多重复。

这样速度快到飞起，在 n=200000 时都可以在 3.98s 内卡过，目前第三优解，吊打一堆分块。