题意:平面上原有一些点,支持动态加点,动态查询与某个点曼哈顿距离最小的点的距离。
这题据说是有 KD-Tree 和 CDQ 分治两种做法,又据说 KDT 会被卡,于是我采用 CDQ (其实是不会 KDT)
考虑给每个加点/查询操作给一个 $t$ 值,作为它的第三个坐标。每次查询先只考虑 $x<x_i,y<y_j,t<t_i$ 的所有点 $(x,y,t)$。对于 $x$ 或 $y$ 的相对大小关系有变的情况,每次沿 $x$ 轴/$y$ 轴翻转,一共做 4 次 CDQ。
$|x_1-x_2|+|y_1-y_2|=(x_1+y_1)-(x_2+y_2)\ (x_1\geq x_2,y_1\geq y_2)$,即对于点 $(x_1,y_1,t_1)$,要找到小于这个点的 $x_2+y_2$ 的最大值。
所有点已经按 $t$ 排好序了。CDQ 合并前后两段区间时按照 $x$ 归并,同时建树状数组以维护 $y<i$ 的点中,$x+y$ 的最大值。
more >>