HDU 3642 Get The Treasury：掃描線 + 線段樹 + 離散化求長方體體積交 ≥ 3 部分

題目大意

給定 n 個長方體（n ≤ 1000），每個由 (x₁,y₁,z₁) 到 (x₂,y₂,z₂) 確定。若某區域被≥ 3 個長方體覆蓋，則該區域確定有寶藏。求寶藏區域的最小體積（即覆蓋次數 ≥ 3 的區域體積和）。座標範圍：|x|,|y| ≤ 10⁶，|z| ≤ 500。

核心思路：降維打擊

1. Z 軸掃描：將長方體投影到 XOY 平面，問題轉化為求平面區域覆蓋 ≥ 3 次的面積
2. 離散化：收集所有 x、z 座標排序去重，建立映射
3. 掃描線 + 線段樹：在每個 z 區間 [zᵢ, zᵢ₊₁) 内，收集該層活躍的長方體投影矩形，用掃描線計算覆蓋 ≥ 3 次的面積
4. 體積累加：面積 × z 高度差

線段樹維護三層覆蓋長度

每個節點維護：

• once：覆蓋 ≥ 1 次的總長度
• twice：覆蓋 ≥ 2 次的總長度
• more：覆蓋 ≥ 3 次的總長度（即我們要的）

三者包含關係：more ⊆ twice ⊆ once。節點另存 cnt 為懶標記（完全覆蓋次數）。

PushUp 邏輯（第二種寫法，包含關係版）

void push_up(int rt, int l, int r) {
    // once：覆蓋 ≥ 1
    if (cnt[rt]) once[rt] = X[r+1] - X[l];
    else if (l == r) once[rt] = 0;
    else once[rt] = once[rt<<1] + once[rt<<1|1];

    // twice：覆蓋 ≥ 2
    if (cnt[rt] > 1) twice[rt] = X[r+1] - X[l];
    else if (l == r) twice[rt] = 0;
    else if (cnt[rt] == 1) twice[rt] = once[rt<<1] + once[rt<<1|1];
    else twice[rt] = twice[rt<<1] + twice[rt<<1|1];

    // more：覆蓋 ≥ 3
    if (cnt[rt] > 2) more[rt] = X[r+1] - X[l];
    else if (l == r) more[rt] = 0;
    else if (cnt[rt] == 2) more[rt] = once[rt<<1] + once[rt<<1|1];
    else if (cnt[rt] == 1) more[rt] = twice[rt<<1] + twice[rt<<1|1];
    else more[rt] = more[rt<<1] + more[rt<<1|1];
}

關鍵洞察：利用包含關係避免重複加減，cnt==2 時 more = 子節點 once 之和（因 once 已含 twice），cnt==1 時 more = 子節點 twice 之和。

完整 AC 代碼

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define ll long long
const int maxn = 2222;
using namespace std;

int cnt[maxn<<2], X[maxn], Z[maxn];
int once[maxn<<2], twice[maxn<<2], more[maxn<<2];

struct Cube {
    struct Pt { int x, y, z; void read() { scanf("%d%d%d", &x, &y, &z); } } a, b;
} cube[maxn];

struct Seg {
    int l, r, h, s; // [l,r) 高度 h, +1 入 / -1 出
    bool operator<(const Seg& o) const { return h < o.h; }
} seg[maxn<<2];

void push_up(int rt, int l, int r) {
    if (cnt[rt]) once[rt] = X[r+1] - X[l];
    else if (l == r) once[rt] = 0;
    else once[rt] = once[rt<<1] + once[rt<<1|1];

    if (cnt[rt] > 1) twice[rt] = X[r+1] - X[l];
    else if (l == r) twice[rt] = 0;
    else if (cnt[rt] == 1) twice[rt] = once[rt<<1] + once[rt<<1|1];
    else twice[rt] = twice[rt<<1] + twice[rt<<1|1];

    if (cnt[rt] > 2) more[rt] = X[r+1] - X[l];
    else if (l == r) more[rt] = 0;
    else if (cnt[rt] == 2) more[rt] = once[rt<<1] + once[rt<<1|1];
    else if (cnt[rt] == 1) more[rt] = twice[rt<<1] + twice[rt<<1|1];
    else more[rt] = more[rt<<1] + more[rt<<1|1];
}

void update(int L, int R, int v, int l, int r, int rt) {
    if (L <= l && r <= R) {
        cnt[rt] += v;
        push_up(rt, l, r);
        return;
    }
    int m = (l + r) >> 1;
    if (L <= m) update(L, R, v, lson);
    if (m < R) update(L, R, v, rson);
    push_up(rt, l, r);
}

void solve(int m) {
    sort(X, X + 2*m);
    sort(Z, Z + 2*m);
    int kx = unique(X, X + 2*m) - X;
    int kz = unique(Z, Z + 2*m) - Z;

    ll ans = 0;
    for (int iz = 0; iz < kz - 1; ++iz) {
        int zLow = Z[iz], zHigh = Z[iz+1];
        int tot = 0;
        for (int i = 0; i < m; ++i) {
            if (cube[i].a.z <= zLow && cube[i].b.z > zLow) {
                int x1 = cube[i].a.x, x2 = cube[i].b.x;
                int y1 = cube[i].a.y, y2 = cube[i].b.y;
                seg[tot++] = {x1, x2, y1, 1};
                seg[tot++] = {x1, x2, y2, -1};
            }
        }
        sort(seg, seg + tot);
        memset(cnt, 0, sizeof(cnt));
        memset(once, 0, sizeof(once));
        memset(twice, 0, sizeof(twice));
        memset(more, 0, sizeof(more));

        for (int i = 0; i < tot - 1; ++i) {
            int l = lower_bound(X, X + kx, seg[i].l) - X;
            int r = lower_bound(X, X + kx, seg[i].r) - X - 1;
            if (l <= r) update(l, r, seg[i].s, 0, kx-1, 1);
            ans += (ll)(zHigh - zLow) * more[1] * (seg[i+1].h - seg[i].h);
        }
    }
    printf("%lld\n", ans);
}

int main() {
    int T, n, cas = 1;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 0; i < n; ++i) {
            cube[i].a.read(); X[2*i] = cube[i].a.x; Z[2*i] = cube[i].a.z;
            cube[i].b.read(); X[2*i+1] = cube[i].b.x; Z[2*i+1] = cube[i].b.z;
        }
        printf("Case %d: ", cas++);
        solve(n);
    }
    return 0;
}

複雜度分析

• 離散化：O(n log n)
• Z 軸枚舉：O(kz) ≤ O(2n)
• 每層掃描線：O(m log m) 排序 + O(m log kx) 線段樹更新
• 總時間：O(n² log n) 最壞，n=1000 约 10⁶~10⁷ 操作，2s 內輕鬆通過
• 空間：O(n)

關鍵技術點總結

1. 三維體積交 → 二維面積交 × 高度，掃描線降維
2. 線段樹維護 ≥k 次覆蓋長度，利用包含關係簡化 PushUp
3. 離散化座標處理大範圍稀疏座標
4. 掃描線事件：矩形底邊 +1，頂邊 -1，按 y 排序
5. 長長整型防溢出：座標 10⁶，體積可達 10¹⁸

測資驗證

輸入：
2
1
0 0 0 5 6 4
3
0 0 0 5 5 5
3 3 3 9 10 11
3 3 3 13 20 45

輸出：
Case 1: 0
Case 2: 8

與 Sample Output 一致。