这是一道二维平面的数点,同时也加上了时间。做过动态逆序对的可能会记得对于 k 维平面、动态加点和询问的题目,可以将时间也当作一个维度,计算 x 轴、 y 轴、时间都更小的点。由于二维平面不可能所有点都在当前点的左下角,所以我们将图掉转做4次 CDQ, 因为是曼哈顿距离,所以用树状数组维护 x+y 的最大值,用询问点的 x+y 减去最大的 x+y 即可,掉转需要计算最大 x 值和 y 值,注意最后要 +1 因为掉转时 x/y 最大的那个点如果掉成 0 树状数组会爆。输入也要+1因为坐标最小为0. 以下是代码: