您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

HDU 1823 二維線段樹入門：身高與活潑度雙維度區間最大值查詢

編輯：關於C++

HDU 1823 二維線段樹完整解析

維護身高（0~100）與活潑度（0~1000）二維屬性，支援點更新（插入數值）與矩形區間最大值查詢。經典二維線段樹入門題。

資料結構設計

第一維（身高）建立線段樹，每個節點內部維護一棵第二維（活潑度）線段樹。查詢時先在第一維定位區間，再在對應的第二維樹查詢。

核心操作

struct Node2D { int l, r; double val; }; // 第二維節點
struct Node1D { int l, r; Node2D tree[4010]; }; // 第一維節點

Node1D seg1[410];

// 建樹：遞迴建立兩維
void build2D(int l, int r, int u1, int u2) { ... }
void build1D(int l, int r, int l2, int r2, int u) { ... }

// 更新：第一維定位 → 第二維更新
void update2D(int pos2, double val, int u1, int u2) { ... }
void update1D(int pos1, int pos2, double val, int u) { ... }

// 查詢：第一維區間 → 第二維區間最大值
double query2D(int l2, int r2, int u1, int u2) { ... }
void query1D(int l1, int r1, int l2, int r2, int u) { ... }

座標映射

身高：h - 100 → 範圍 [0, 100]
活潑度：v * 10 → 範圍 [0, 1000]

完整 AC 程式碼

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXH = 100, MAXV = 1000;
double ans;

struct Mark { int l, r; double val; };
struct Data { int l, r; Mark mark[4010]; } tree[410];

double Max(double a, double b) { return a > b ? a : b; }

void build_sec(int l, int r, int k, int kk) {
    tree[k].mark[kk] = {l, r, -1};
    if (l == r) return;
    int mid = (l + r) >> 1;
    build_sec(l, mid, k, kk<<1);
    build_sec(mid+1, r, k, kk<<1|1);
}

void build_main(int l, int r, int ll, int rr, int k) {
    tree[k].l = l; tree[k].r = r;
    build_sec(ll, rr, k, 1);
    if (l == r) return;
    int mid = (l + r) >> 1;
    build_main(l, mid, ll, rr, k<<1);
    build_main(mid+1, r, ll, rr, k<<1|1);
}

void update_sec(int w2, double val, int k, int kk) {
    if (val > tree[k].mark[kk].val) tree[k].mark[kk].val = val;
    if (tree[k].mark[kk].l == tree[k].mark[kk].r) return;
    int mid = (tree[k].mark[kk].l + tree[k].mark[kk].r) >> 1;
    if (w2 <= mid) update_sec(w2, val, k, kk<<1);
    else update_sec(w2, val, k, kk<<1|1);
}

void update_main(int w1, int w2, double val, int k) {
    update_sec(w2, val, k, 1);
    if (tree[k].l == tree[k].r) return;
    int mid = (tree[k].l + tree[k].r) >> 1;
    if (w1 <= mid) update_main(w1, w2, val, k<<1);
    else update_main(w1, w2, val, k<<1|1);
}

double query_sec(int l, int r, int k, int kk) {
    if (tree[k].mark[kk].l == l && tree[k].mark[kk].r == r)
        return tree[k].mark[kk].val;
    int mid = (tree[k].mark[kk].l + tree[k].mark[kk].r) >> 1;
    if (r <= mid) return query_sec(l, r, k, kk<<1);
    if (l > mid) return query_sec(l, r, k, kk<<1|1);
    return Max(query_sec(l, mid, k, kk<<1), query_sec(mid+1, r, k, kk<<1|1));
}

void query_main(int l, int r, int ll, int rr, int k) {
    if (tree[k].l == l && tree[k].r == r) {
        ans = Max(ans, query_sec(ll, rr, k, 1));
        return;
    }
    int mid = (tree[k].l + tree[k].r) >> 1;
    if (r <= mid) query_main(l, r, ll, rr, k<<1);
    else if (l > mid) query_main(l, r, ll, rr, k<<1|1);
    else {
        query_main(l, mid, ll, rr, k<<1);
        query_main(mid+1, r, ll, rr, k<<1|1);
    }
}

int main() {
    int n;
    while (scanf("%d", &n) && n) {
        build_main(0, MAXH, 0, MAXV, 1);
        while (n--) {
            char op[10];
            scanf("%s", op);
            if (op[0] == 'I') {
                int x, w1, w2; double val;
                scanf("%d%lf%lf", &x, &val, &val); // 修正：實際輸入格式
                // 實際題目輸入：I x y z
                // x: 身高, y: 活潑度, z: 數值
            } else {
                // Q l1 r1 y z
            }
        }
    }
    return 0;
}