UVa12389/LA5821 Cybercrime Donut Investigation

题目链接

  本题是2011年icpc欧洲区域赛西南欧赛区的C题

题意

  查询多个目标点与参考点集中最近点的曼哈顿距离。

输入格式

  多组数组，每组数据的第一行是整数 n (1 ≤ n ≤ 100, 000)，表示参考点的数量。接下来 n 行每行两个整数表示各个参考点的坐标。接下来一行是整数 q (1 ≤ q ≤ 50, 000)，表示目标点的数量。接下来 q 行每行两个整数表示各个目标点的坐标。所有点的坐标 $x,y$ 都满足 $1\le x,y\le 10^9$。
  不同测试数据之间有一个空行。最后一行用“-1”表示输入结束。

输出格式

  对每组数据输出 q 行，每行依次输出各个目标点与参考点集中最近点的曼哈顿距离。相邻两组输出用一个空行分隔。

分析

  本题可以用 k-D Tree 来做。不过还可以用树状数组来做，效率更高。

k-D Tree 解法

  k-D Tree 的每棵子树维护横纵坐标的最大最小值 $x1,x2,y1,y2$，建树的时间复杂度是 $O(n\log n)$。
  查询可以这样做：目标点与根节点坐标的曼哈顿距离作为答案的初值 $d$ ；如果目标点到左子树的矩形边界距离最小值 $dl<d$ 则递归左子树并更新 $d$；如果目标点到右子树的矩形边界距离最小值 $dr<d$ 则递归右子树并更新 $d$。
  查询的时间复杂度最好是 $O(1)$，最差是 $O(n)$，平均可能是 $O(\sqrt{n})$（平均时间复杂度未作严谨分析）。

树状数组解法

  考虑参考点 $(x_j,y_j)$ 在目标点 $(x_i,y_i)$ 左下、左上、右下、右上四种情况，将曼哈顿距离 $\left|x_i-x_j\right|+\left|y_i-y_j\right|$ 去绝对值。
  参考点在目标点左下时$$\left|x_i-x_j\right|+\left|y_i-y_j\right|=x_i-x_j+y_i-y_j=(x_i+y_i)-(x_j+y_j)$$  可见，参考点在目标点左下时，曼哈顿距离最小值为 x i + y i − m a x { x j + y j } x_i+y_i-max\{x_j+y_j\} xi​+yi​−max{xj​+yj​}，也就是说对每个目标点 $(x_i,y_i)$ 由于其 $x_i+y_i$ 已知，只需要找出其左下那些参考点 $(x_j,y_j)$ 的 $x_j+y_j$ 最大值即可得到目标点离这部分参考点的曼哈顿距离最小值。
  同理，参考点在目标点左上时，曼哈顿距离最小值为 x i − y i − m a x { x j − y j } x_i-y_i-max\{x_j-y_j\} xi​−yi​−max{xj​−yj​}。
  同理，参考点在目标点右下时，曼哈顿距离最小值为 − x i + y i − m a x { − x j + y j } -x_i+y_i-max\{-x_j+y_j\} −xi​+yi​−max{−xj​+yj​}。
  同理，参考点在目标点右上时，曼哈顿距离最小值为 − x i − y i − m a x { − x j − y j } -x_i-y_i-max\{-x_j-y_j\} −xi​−yi​−max{−xj​−yj​}。

  至此，树状数组解法可以想到了：

1. 将参考点和目标点放到一个数组 points 中，按照横坐标排序。再把所有这些点的 y 值排序并去重得到数组 Y，记数组 Y 的大小为 t 。对所有目标点 $(x_i,y_i)$，初始化答案 $ans[i]=\infty$。
2. 初始化两个树状数组 $c_1、c_2$，其大小都和数组 Y 相同，均为 t，每个元素的初始值均为 $-\infty$。
3. 顺序遍历数组 points，对当前点 $(x_i,y_i)$，计算 $v1=x[i]+y[i],v2=x[i]-y[i]$ 并找出 $y_i$ 在数组 Y 中的位置 p（位置需要从1开始编号）
   3.1 若当前点是参考点，则更新树状数组 $c_1、c_2$

   for (int x = p; x <= t; x += x&-x) c1[x] = max(c1[x], v1);
   for (int x = p; x > 0; x -= x&-x) c2[x] = max(c2[x], v2);
   

   3.2 若当前点是目标点，则更新答案 $ans[i]$

   for (int x = p; x > 0; x -= x&-x) ans[i] = min(ans[i], v1 - c1[x]);
   for (int x = p; x <= t; x += x&-x) ans[i] = min(ans[i], v2 - c2[x]);
   

4. 将两个树状数组 $c_1、c_2$ 的每个元素初始值均重置回 $-\infty$。
5. 逆序遍历数组 points，对当前点 $(x_i,y_i)$，计算 $v1=-x[i]+y[i],v2=-x[i]-y[i]$ 并找出 $y_i$ 在数组 Y 中的位置 p（位置需要从1开始编号）。当前点如果是参考点，则同 3.1 更新树状数组 $c_1、c_2$；否则同 3.2 更新答案 $ans[i]$。

  注意：题面交代“所有点的坐标 $x,y$ 都满足 $1\le x,y\le 10^9$”，因此 3.2 步中 “v1 - c1[x]、v2 - c2[x]” 这两个运算当 v1、c1[x]、c2[x] 都用 int 保存时可能会有溢出。解决办法是检查“c1[x]、c2[x]”，当其为 $-\infty$ 时不更新答案 $ans[i]$（此时也说明目标点左下、左上、右下、右上对应象限内无参考点）。

AC 代码

k-D Tree 版本

#include <iostream>
#include <algorithm>
using namespace std;

#define N 100100
#define T 150100
int a[N], x[T], y[T], lc[N], rc[N], p[N], x1[N], x2[N], y1[N], y2[N], n, q, t, kase = 0;

bool cmpx(int i, int j) {
    return x[i] < x[j] || (x[i] == x[j] && y[i] < y[j]);
}

bool cmpy(int i, int j) {
    return y[i] < y[j] || (y[i] == y[j] && x[i] < x[j]);
}

void update(int o, int ch) {
    x1[o] = min(x1[o], x1[ch]); x2[o] = max(x2[o], x2[ch]); y1[o] = min(y1[o], y1[ch]); y2[o] = max(y2[o], y2[ch]);
}

void build(int& o, int l, int r, int d = 0) {
    o = ++t; lc[o] = rc[o] = 0;
    if (l < r) {
        int m = (l+r)>>1; nth_element(a+l, a+m, a+r, d&1 ? cmpy : cmpx);
        p[o] = a[m]; x1[o] = x2[o] = x[a[m]]; y1[o] = y2[o] = y[a[m]];
        if (l < m) build(lc[o], l, m-1, d^1), update(o, lc[o]);
        build(rc[o], m+1, r, d^1); update(o, rc[o]);
    } else p[o] = a[l], x1[o] = x2[o] = x[a[l]], y1[o] = y2[o] = y[a[l]];
}

int check(int x1, int x2, int y1, int y2, int xi, int yi) {
    if (xi < x1) return yi < y1 ? max(x1-xi, y1-yi) : (yi > y2 ? max(x1-xi, yi-y2) : x1-xi);
    if (xi > x2) return yi < y1 ? max(xi-x2, y1-yi) : (yi > y2 ? max(xi-x2, yi-y2) : xi-x2);
    return yi < y1 ? y1-yi : (yi > y2 ? yi-y2 : 0);
}

int query(int o, int l, int r, int i, int d = 0) {
    int ans = max(abs(x[p[o]]-x[i]), abs(y[p[o]]-y[i])), m = (l+r)>>1;
    if (ans == 0) return ans;
    bool f = d&1 ? cmpy(i, p[o]) : cmpx(i, p[o]); int c1 = f ? lc[o] : rc[o], c2 = f ? rc[o] : lc[o];
    if (c1 && check(x1[c1], x2[c1], y1[c1], y2[c1], x[i], y[i]) < ans)
        ans = min(ans, query(c1, f ? l : m+1, f ? m-1 : r, i, d^1));
    if (c2 && check(x1[c2], x2[c2], y1[c2], y2[c2], x[i], y[i]) < ans)
        ans = min(ans, query(c2, f ? m+1 : l, f ? r : m-1, i, d^1));
    return ans;
}

void query(int i) {
    cin >> x[i] >> y[i]; t = x[i]+y[i]; x[i] -= y[i]; y[i] = t;
    cout << query(1, 1, n, i) << endl;
}

void solve() {
    if (kase++) cout << endl;
    for (int i=1; i<=n; ++i) cin >> x[i] >> y[i], t = x[i]+y[i], x[i] -= y[i], y[i] = t, a[i] = i;
    int s = t = 0; build(s, 1, n);
    cin >> q;
    for (int i=1; i<=q; ++i) query(n+i);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    while (cin >> n && n != -1) solve();
    return 0;
}

树状数组版本

#include <iostream>
#include <algorithm>
using namespace std;

#define Q 50010
#define M 150020
int a[M], x[M], y[M], z[M], c1[M], c2[M], d[Q], n, q, t, kase = 0, INF = 0x7f7f7f7f;

bool cmp(int i, int j) {
    return x[i] < x[j];
}

void update(int x, int type, int v) {
    if (type) while (x > 0) c1[x] = max(c1[x], v), x -= x&-x;
    else while (x <= t) c2[x] = max(c2[x], v), x += x&-x;
}

void query(int x, int type, int v, int& r) {
    int s = -INF;
    if (type) while (x <= t) s = max(s, c1[x]), x += x&-x;
    else while (x > 0) s = max(s, c2[x]), x -= x&-x;
    if (s > -INF) r = min(r, v-s);
}

void solve() {
    if (kase++) cout << endl;
    for (int i=0; i<n; ++i) cin >> x[i] >> y[i], z[i] = y[i], a[i] = i;
    cin >> q; q += n;
    for (int i=n; i<q; ++i) cin >> x[i] >> y[i], z[i] = y[i], a[i] = i, d[i-n] = INF;
    sort(a, a+q, cmp); sort(z, z+q); t = unique(z, z+q) - z;
    for (int i=1; i<=t; ++i) c1[i] = c2[i] = -INF;
    for (int i=0; i<q; ++i) {
        int p = upper_bound(z, z+t, y[a[i]]) - z;
        if (a[i] < n) update(p, 0, x[a[i]]+y[a[i]]), update(p, 1, x[a[i]]-y[a[i]]);
        else query(p, 0, x[a[i]]+y[a[i]], d[a[i]-n]), query(p, 1, x[a[i]]-y[a[i]], d[a[i]-n]);
    }
    for (int i=1; i<=t; ++i) c1[i] = c2[i] = -INF;
    for (int i=q-1; i>=0; --i) {
        int p = upper_bound(z, z+t, y[a[i]]) - z;
        if (a[i] < n) update(p, 0, y[a[i]]-x[a[i]]), update(p, 1, -x[a[i]]-y[a[i]]);
        else query(p, 0, y[a[i]]-x[a[i]], d[a[i]-n]), query(p, 1, -x[a[i]]-y[a[i]], d[a[i]-n]);
    }
    for (int i=0, j=q-n; i<j; ++i) cout << d[i] << endl;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    while (cin >> n && n != -1) solve();
    return 0;
}