Description

需要维护一个结构,要求支持以下2个操作。

  1. 向二位空间内插入一个点。
  2. 给出一个二维点,询问距离这个点曼哈顿距离最近的点的曼哈顿距离。

$n, m ≤ 3 × 10^5 , T = 3s$

Idea

本题可以使用 kd-tree 加上替罪羊树做到按题意模拟,但是我还不太会。

所以我们用 CDQ 分治解决这个问题。

对于每个要查询的点,二维空间被它分割成四个象限,我们只考虑第三象限的做法,然后不断翻转即可。

这样我们去掉了曼哈顿距离中的绝对值,将题目转化为一个简单的三维偏序问题:

对于一个询问 $(x, y)$,找到满足时间戳在其前且 $x_i \le x, y_i \le y$ 的点中 $x_i + y_i$​ 的最大值。

至于具体的实现,还是看代码吧。

Code

Leave a Reply to kal0rona

  1. kal0rona
    Dec 27, 2018

    tql

    Reply