Menci

眉眼如初,岁月如故

在那无法确定的未来
只愿真心如现在一般清澈


「BZOJ 2716」天使玩偶 - CDQ

维护一个平面,支持以下两种操作:

  1. 加入点 (x, y) (x,\ y)
  2. 查询麦哈顿距离与点 (x, y) (x,\ y) 最小的点。

链接

BZOJ 2716

题解

任意两个点 (x1, y1) (x_1,\ y_1) (x2, y2) (x_2,\ y_2) 的麦哈顿距离为 x1x2+y1y2 | x_1 - x_2 | + | y_1 - y_2 |

(x1, y1) (x_1,\ y_1) (x2, y2) (x_2,\ y_2) 左下方时,其麦哈顿距离为:

x1x2+y1y2=(x1x2)+(y1y2)=(x1+y1)(x2+y2) \begin{aligned} & | x_1 - x_2 | + | y_1 - y_2 | \\ =& ( x_1 - x_2 ) + ( y_1 - y_2 ) \\ =& ( x_1 + y_1 ) - (x_2 + y_2) \end{aligned}

问题转化为数据结构维护 (x2+y2) (x_2 + y_2) 的最大值,很明显这是一个三维偏序问题,可以使用 CDQ 分治解决,将传统的 CDQ 分治中的累加改为取较小值即可。

代码

#include <cstdio>
#include <climits>
#include <algorithm>

const int MAXN = 500000;
const int MAXM = 500000;
const int MAXX = 1000000;

struct Triple {
    int id, x, y, *ans;

    Triple() {}

    Triple(const int x, const int y, int *ans = NULL) : x(x), y(y), ans(ans) {
        static int i = 0;
        id = i++;
    }
} a[MAXN + MAXM];

bool operator<(const Triple &a, const Triple &b) {
    return a.id < b.id;
}

int maxX, maxY;

struct BinaryIndexedTree {
    int a[MAXX + 2];

    static int lowbit(const int x) { return x & -x; }

    int query(const int x) const {
        int ans = 0;
        for (int i = x; i > 0; i -= lowbit(i)) ans = std::max(ans, a[i - 1]);
        return ans;
    }

    void update(const int x, const int v) {
        for (int i = x; i <= maxY; i += lowbit(i)) a[i - 1] = std::max(a[i - 1], v);
    }

    void clear(const int x) {
        for (int i = x; i <= maxY; i += lowbit(i)) {
            if (a[i - 1]) a[i - 1] = 0;
            else break;
        }
    }
} bit;

inline void cdq(Triple *l, Triple *r) {
    if (l == r) return;

    Triple *mid = l + (r - l) / 2;

    cdq(l, mid);
    cdq(mid + 1, r);

    static Triple tmp[MAXN + MAXM];
    for (Triple *q = tmp, *p1 = l, *p2 = mid + 1; q <= tmp + (r - l); q++) {
        if ((p1 <= mid && p1->x <= p2->x) || p2 > r) {
            *q = *p1++;
            if (!q->ans) bit.update(q->y, q->x + q->y);
        } else {
            *q = *p2++;
            if (q->ans) {
                int res = bit.query(q->y);
                if (res) *q->ans = std::min(*q->ans, q->x + q->y - res);
            }
        }
    }

    for (Triple *q = tmp, *p = l; p <= r; p++, q++) {
        *p = *q;
        bit.clear(p->y);
    }
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    int cnt = 0;
    for (int i = 0; i < n; i++) {
        int x, y;
        scanf("%d %d\n", &x, &y), x += 2, y += 2;
        a[cnt++] = Triple(x, y);

        maxX = std::max(maxX, x);
        maxY = std::max(maxY, y);
    }

    static int ans[MAXM];
    int qCnt = 0;
    for (int j = 0; j < m; j++) {
        int t, x, y;
        scanf("%d %d %d", &t, &x, &y), x += 2, y += 2;
        if (t == 1) {
            a[cnt++] = Triple(x, y);
        } else {
            a[cnt++] = Triple(x, y, &ans[qCnt++]);
        }

        maxX = std::max(maxX, x);
        maxY = std::max(maxY, y);
    }

    for (int i = 0; i < qCnt; i++) ans[i] = INT_MAX;

    cdq(a, a + cnt - 1);

    for (int i = 0; i < cnt; i++) a[i].x = maxX - a[i].x + 1;
    std::sort(a, a + cnt);
    cdq(a, a + cnt - 1);

    for (int i = 0; i < cnt; i++) a[i].y = maxY - a[i].y + 1;
    std::sort(a, a + cnt);
    cdq(a, a + cnt - 1);

    for (int i = 0; i < cnt; i++) a[i].x = maxX - a[i].x + 1;
    std::sort(a, a + cnt);
    cdq(a, a + cnt - 1);

    for (int i = 0; i < qCnt; i++) printf("%d\n", ans[i]);

    return 0;
}
最近的文章

「BZOJ 2438」杀人游戏 - 强联通分量

一位杀手潜入假装成平民。警察希望能在 N N 个人里面,查出谁是杀手。警察能够对每一个人进行查证,假如查证的对象是平民,他会告诉警察,他认识的人,谁是杀手,谁是平民。假如查证的对象是杀手,杀手将会把警察干掉。

现在警察掌握了每一个人认识谁。每一个人都有可能是杀手,可看作他们是杀手的概率是相同的。

根据最优的情况,保证警察自身安全并知道谁是杀手的概率最大是多少?

于  BZOJ, Tarjan, 强联通分量, 缩点 继续阅读
更早的文章

「SHOI2007」园丁的烦恼 - CDQ

每一棵树可以用一个整数坐标来表示,每次询问你某一个矩阵内有多少树。

于  BZOJ, CDQ, SHOI, 分治, 数据结构, 树状数组 继续阅读
comments powered by Disqus