题解 P3635 【[APIO2012]苦无】

JoshAlMan · 2020-11-22 17:41:42 · 题解

这题网上貌似还没有完整的题解呢，我来口胡一下~

Description

W \times H$ 的二维坐标系，$W, H \le 10^9

给 n (n \le 10^5) 个点 (x, y)，每个点有个方向，每 1 时刻箭头朝其位置移动一个单位，如果点相遇就会消失。问点经过轨迹的格子并。

Solution

整体框架分析

如果我们能快速确定每个苦无运动的轨迹（最终在何时刻消失），之后的问题是矩形面积并，用扫描线 O(n \log n) 解决。

首先我们可以发现，如果不考虑苦无的消失，两个苦无相撞的充要条件即在一条横线、竖线或斜线（呈 45° 角）上，然后满足一些方向限制，比如，左右相撞的苦无 i, j 要满足在同一条横线 X_i = Y_i，然后 Y_i < Y_j, D_i = 0, D_j = 2。

令我们比较困扰的事，可能两个苦无满足上述条件，但在此之前其中有苦无已经消失了，所以这次相遇就失败了。

我们可以按照时间顺序处理，每次把冲突时间最短的若干苦无都拿出来然后让他们消失，如果我们遇到的相遇事件中又苦无已经消失了，就跳过。

快速维护 & 算出最短相撞的苦无

由于每个点分别在一条横线、竖线、斜线上，所以我们可以把每条这样的线及方向当成一个集合，每个点至多在四个集合中。

然后我们现在的问题就变成了：一个数轴上，每个位置可能有两种种类的点（0, 1），然后要求最近匹配的 01 点对（方向不能反），还要支持删除点。

如果我们考虑每个点匹配的最优点，我们是可以通过 \text{set} 在 \log 时间算出前驱后继，但删除一个点的时候，可能有多个点的最有匹配是他，要修改多个点，这样就挂了。不妨考虑双向匹配，我们维护 x, y 互相都作为对方的最优匹配这样的点对，这样是对的，因为单向匹配总能找到更优的双向匹配。所以在删除的一个点的时候，如果他在双向匹配里，让他的匹配点找新的匹配，即可。

这样时间复杂度就是 O(n \log n)

接下来的工作就是把双向匹配放进一个堆里，每次把所有时间最短的点拿出来删除就行。

一些细节

关于横竖直线，距离为奇数点的相撞时间问题。比如相邻的两个 → ←，如果右箭头上方有一个下箭头（如题面右下角的图），那个箭头不会相撞，说明相撞时间 > 1，但如果相撞时间又得 < 2，否则会和左箭头相撞，因此这种的相撞时间应该是 1.5。我是把时间整体 \times 2，这样就可以没有小数。
一定要每次把所有同一时间的点一块删除，不然可能会存在同一时间，但后者认为前者已经消失的恐怖方法。

时间复杂度

O(n \log n)

Code

感觉自己确实写的很麻烦，其实独自开个结构体维护那个数轴可能会更简单一点。

#include <iostream>
#include <cstdio>
#include <set>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

typedef long long LL;

const int N = 100005, INF = 2e9;

int W, H, n, X[N], Y[N], D[N], L[N][4], f[N], m, a[N << 1], len, d[4][N], tot[4];
int nxt[4][4], pre[4][4], match[N][4], val[N][4], stk[N], top;
LL ans;
bool st[N], re[N];

struct O {
    int v, x, y;
    bool operator < (const O &b) const { return v > b.v; }
};

struct Node{
    int x, id;
    bool operator < (const Node &b) const { return x < b.x; }
};

typedef set<Node>::iterator SIT;

set<Node> s[4][N][4];
// 第一维：横 / 竖 / 左下 - 右上 / 左上 / 右下; 第二维：离散后线编号; 第三维：存储的方向值
priority_queue<O> q;

int inline get(int x, int o) { return lower_bound(d[o] + 1, d[o] + 1 + tot[o], x) - d[o]; }

void inline find(int c, int i) {
    match[i][c] = 0;
    int x = L[i][c], k = c == 0 ? Y[i] : X[i];
    if (nxt[c][D[i]] != -1) {
        int cq = nxt[c][D[i]];
        SIT it = s[c][x][cq].lower_bound( (Node) { k, 0 } );
        if (it != s[c][x][cq].end()) {
            int j = it -> id, w = (it -> x - k + 1) * 2;
            if (c < 2) w = w / 2 + 1; 
            if (!match[j][c] || w < val[j][c]) {
                match[i][c] = j, match[j][c]  = i, val[i][c] = val[j][c] = w;
                q.push((O){ val[i][c], i, j });
            }
        }
    } 
    if (pre[c][D[i]] != -1) {
        int cq = pre[c][D[i]];
        SIT it = s[c][x][cq].lower_bound( (Node) { k, 0 } );
        if (it != s[c][x][cq].begin()) {
            --it; int j = it -> id, w = (k - it -> x + 1) * 2;
            if (c < 2) w = w / 2 + 1; 
            if (!match[j][c] || w < val[j][c]) {
                match[i][c] = j, match[j][c]  = i, val[i][c] = val[j][c] = w;
                q.push((O){ val[i][c], i, j });
            }
        }
    }
}

void inline insert(int c, int i) {
    int x = L[i][c], k = c == 0 ? Y[i] : X[i];
    s[c][x][D[i]].insert((Node) { k, i } );
    find(c, i);
}

void inline init() {
    memset(nxt, -1, sizeof nxt);
    memset(pre, -1, sizeof pre);
    nxt[0][0] = 2, pre[0][2] = 0, nxt[1][3] = 1, pre[1][1] = 3;
    pre[2][0] = 3, nxt[2][3] = 0, pre[2][1] = 2, nxt[2][2] = 1;
    nxt[3][0] = 1, pre[3][1] = 0, nxt[3][3] = 2, pre[3][2] = 3;
    for (int i = 1; i <= n; i++) {
        d[0][++tot[0]] = X[i], d[1][++tot[1]] = Y[i];
        d[2][++tot[2]] = X[i] + Y[i], d[3][++tot[3]] = X[i] - Y[i];
    }
    for (int i = 0; i < 4; i++) {
        sort(d[i] + 1, d[i] + 1 + tot[i]);
        tot[i] = unique(d[i] + 1, d[i] + 1 + tot[i]) - d[i] - 1;
    }
    for (int i = 1; i <= n; i++) {
        L[i][0] = get(X[i], 0), L[i][1] = get(Y[i], 1);
        L[i][2] = get(X[i] + Y[i], 2), L[i][3] = get(X[i] - Y[i], 3);
        for (int j = 0; j < 4; j++) insert(j, i);
    }
}

void inline del(int i) {
    if (re[i]) return;
    re[i] = true;
    for (int c = 0; c < 4; c++) {
        int x = L[i][c], k = c == 0 ? Y[i] : X[i];
        s[c][x][D[i]].erase((Node) { k, i } );
        if (match[i][c]) find(max(nxt[c][D[i]], pre[c][D[i]]), match[i][c]);
    }
}

void inline clear() { while (!q.empty() && (st[q.top().x] || st[q.top().y])) q.pop(); }

void inline work() {
    while (!q.empty()) {
        clear();
        if (q.empty()) break;
        int v = q.top().v;
        while (1) {
            clear();
            if (q.empty() || q.top().v != v) break;
            O u = q.top(); 
            f[u.x] = f[u.y] = v >> 1, del(u.x), del(u.y);
            stk[++top] = u.x, stk[++top] = u.y; q.pop();
        }
        while (top) st[stk[top--]] = true;
    }
}

struct E{
    int x, l, r, c;
    bool operator < (const E &b) const { return x < b.x; }
} e[N << 1];

void inline add(int x1, int y1, int x2, int y2) {
    e[++m] = (E) { x1, y1, y2 + 1, 1 };
    e[++m] = (E) { x2 + 1, y1, y2 + 1, -1 };
    a[++len] = y2 + 1, a[++len] = y1;
}

int inline getY(int y) {
    return lower_bound(a + 1, a + 1 + len, y) - a;
}

struct T{
    int len, cnt;
} t[N * 8];

void inline pushup(int p, int l, int r) {
    t[p].len = t[p].cnt ? a[r + 1] - a[l] : t[p << 1].len + t[p << 1 | 1].len;
}

void change(int p, int l, int r, int x, int y, int k) {
    if (x <= l && r <= y) {
        t[p].cnt += k;
        if (l == r) t[p].len = t[p].cnt ? a[r + 1] - a[r] : 0;
        else pushup(p, l, r); 
        return;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) change(p << 1, l, mid, x, y, k);
    if (mid < y) change(p << 1 | 1, mid + 1, r, x, y, k);
    pushup(p, l, r);
}

void inline fill() {
    for (int i = 1; i <= n; i++) {
        if (D[i] == 0) add(X[i], Y[i], X[i], Y[i] + f[i] - 1);
        else if (D[i] == 1)  add(X[i] - f[i] + 1, Y[i], X[i], Y[i]);
        else if (D[i] == 2) add(X[i], Y[i] - f[i] + 1, X[i], Y[i]);
        else add(X[i], Y[i], X[i] + f[i] - 1, Y[i]);
    }
    sort(e + 1, e + 1 + m);
    sort(a + 1, a + 1 + len);
    len = unique(a + 1, a + 1 + len) - a - 1;
    for (int i = 1; i <= m; i++) {
        change(1, 1, len, getY(e[i].l), getY(e[i].r) - 1, e[i].c);
        if (i != m && e[i].x != e[i + 1].x)
            ans += (e[i + 1].x - e[i].x) * (LL)t[1].len;
    }
}

int main() {
    scanf("%d%d%d", &W, &H, &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%d", Y + i, X + i, D + i);
        if (D[i] == 0) f[i] = W - Y[i] + 1;
        else if (D[i] == 1) f[i] = X[i];
        else if (D[i] == 2) f[i] = Y[i];
        else f[i] = H - X[i] + 1;
    }
    init(); 
    work();
    fill();
    printf("%lld\n", ans);
    return 0;
}

题解 P3635 【[APIO2012]苦无 】