按照套路,可以用 DFS 序把问题转化成询问覆盖一个点的所有矩形中的第 k 小权值。
这个别人都讲烂了。
然后,就可以用数据结构维护辣!
但是为什么大家都写了整体二分……
我永远喜欢树套树!
于是我选择了用树套树维护扫描线。
但是这样子卡不过去。
我用了一些卡常的技巧: - 读入优化。 - 权值离散化,单次操作从 O(lognlogc) 降到了 O(lognlogp)。 - 发现我们不用每个矩形都存两个(旋转 90∘),而是保证所有坐标点 (x,y) 都满足 x≤y,这样就只用存一个矩形。
于是这样子就能通过了。
代码:
1 |
|