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

UVA 11992 二維線段樹：矩陣區間加/賦值/查詢和/最大/最小

編輯：關於C++

問題描述

R 行 C 列矩陣（R,C ≤ 50000？實際 R≤20，C≤50000），初始全 0。三種操作：

區間加：子矩陣 [x1,x2]×[y1,y2] 所有元素 +v
區間賦值：子矩陣所有元素 =v
區間查詢：子矩陣和、最大值、最小值

解法：每行一棵線段樹

R 較小（≤20），可為每行維護一棵 1D 線段樹，支援區間加/賦值懶標記、區間查詢。操作時遍歷涉及的行，對每行調用線段樹操作。

線段樹節點結構

struct Node {
    int sum, mn, mx;
    int add, set;  // set=-1 表示無賦值標記
    // 區間長度 len = r-l+1
    void apply_add(int v, int len) {
        sum += v * len;
        mn += v; mx += v;
        add += v;
    }
    void apply_set(int v, int len) {
        sum = v * len;
        mn = mx = v;
        set = v; add = 0;
    }
};

關鍵操作：pushdown 與 pushup

void pushdown(int rt, int l, int r) {
    int lc = rt<<1, rc = rt<<1|1, mid = (l+r)>>1;
    if (set[rt] != -1) {
        // 賦值標記優先級高，覆蓋子節點所有標記
        apply_set(lc, set[rt], mid-l+1);
        apply_set(rc, set[rt], r-mid);
        set[rt] = -1;
    }
    if (add[rt] != 0) {
        apply_add(lc, add[rt], mid-l+1);
        apply_add(rc, add[rt], r-mid);
        add[rt] = 0;
    }
}

void pushup(int rt) {
    sum[rt] = sum[rt<<1] + sum[rt<<1|1];
    mn[rt] = min(mn[rt<<1], mn[rt<<1|1]);
    mx[rt] = max(mx[rt<<1], mx[rt<<1|1]);
}

完整代碼框架

#include 
using namespace std;
const int MAXC = 50005;
const int INF = 0x3f3f3f3f;

struct SegTree {
    int sum[MAXC<<2], mn[MAXC<<2], mx[MAXC<<2];
    int add[MAXC<<2], setv[MAXC<<2];
    int n;
    
    void init(int _n) { n = _n; build(1, 1, n); }
    void build(int rt, int l, int r) {
        add[rt] = 0; setv[rt] = -1;
        sum[rt] = mn[rt] = mx[rt] = 0;
        if (l == r) return;
        int mid = (l+r)>>1;
        build(rt<<1, l, mid);
        build(rt<<1|1, mid+1, r);
    }
    // pushdown, pushup, update, query 如前所述...
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int R, C, Q;
    while (cin >> R >> C >> Q) {
        vector rows(R+1);
        for (int i = 1; i <= R; ++i) rows[i].init(C);
        
        while (Q--) {
            int op, x1, y1, x2, y2, v;
            cin >> op >> x1 >> y1 >> x2 >> y2;
            if (op < 3) cin >> v;
            if (x1 > x2) swap(x1, x2);
            if (y1 > y2) swap(y1, y2);
            
            if (op == 1) {  // 加
                for (int i = x1; i <= x2; ++i) rows[i].update(y1, y2, v);
            } else if (op == 2) {  // 賦值
                for (int i = x1; i <= x2; ++i) rows[i].update_set(y1, y2, v);
            } else {  // 查詢
                long long sum = 0; int mn = INF, mx = -INF;
                for (int i = x1; i <= x2; ++i) {
                    auto [s, mi, ma] = rows[i].query(y1, y2);
                    sum += s; mn = min(mn, mi); mx = max(mx, ma);
                }
                cout << sum << ' ' << mn << ' ' << mx << '\n';
            }
        }
    }
    return 0;
}