题解：CF44G Shooting Gallery
Underage_potato · · 题解
Sol
给出一些矩形，每个矩形都有一个高度，保证高度互不相同。
有若干次从下到上的射击，会击中并摧毁射击点上最低的那个矩形。
求出每次射击击中的矩形，或指出未射中。
使用 KDT 解决本题。
我们将每个矩形视作 KDT 上的一个节点，对于空间的划分则依据矩形的中心点
对于每个 KDT 节点需要维护两类信息：
- 自身信息，即该矩形的四个边界以及其编号和高度。
- 子树信息，该子树内所有矩形的的并的四个边界，如果射击点
(x,y) 不在这个范围内，说明该子树内没有任何矩形能覆盖射击点，直接剪枝。以及，该子树内所有未删除矩形的最小高度。如果当前子树的最小高度已经大于等于我们目前找到的最优解，直接剪枝。
而对于删除操作，可以不直接删除节点，而是把高度设为一个极大值，这样便不会影响答案，同时更新祖先记录的信息即可。
时间复杂度
Code