UVA 11992 Fast Matrix Operations：二維線段樹/一維化區間加蓋操作

線段樹支持：區間加 + 區間賦值 + 區間查詢

需同時維護 sum、min、max，且賦值操作優先級高於加法（賦值清除舊加法標記）。

節點結構

struct Node {
    ll sum, mn, mx;
    ll add_tag;   // 區間加標記
    ll set_tag;   // 區間賦值標記，-1 表示無
    bool has_set() { return set_tag != -1; }
};

關鍵操作

• PushDown：先推賦值標記（覆蓋子節點的加/賦值），再推加法標記。
• Maintain：根據子節點與當前標記更新 sum/mn/mx。
• UpdateAdd / UpdateSet：標準區間更新。
• Query：遞歸收集 sum/mn/mx，傳遞累積加法標記。

完整代碼框架

class SegTree {
    vector t;
    int n;
    void apply_set(int o, int l, int r, ll v) { ... }
    void apply_add(int o, int l, int r, ll v) { ... }
    void push_down(int o, int l, int r) { ... }
    void maintain(int o, int l, int r) { ... }
    void update_add(int o, int l, int r, int L, int R, ll v) { ... }
    void update_set(int o, int l, int r, int L, int R, ll v) { ... }
    void query(int o, int l, int r, int L, int R, ll add_acc, Res& res) { ... }
public:
    SegTree(int _n) : n(_n) { t.resize(4*n); build(1,1,n); }
    void add(int l, int r, ll v) { update_add(1,1,n,l,r,v); }
    void set(int l, int r, ll v) { update_set(1,1,n,l,r,v); }
    Res ask(int l, int r) { Res res; query(1,1,n,l,r,0,res); return res; }
};

主程序處理

while (scanf("%d%d%d", &R, &C, &M) == 3) {
    SegTree st(R * C);
    for (int q = 0; q < M; ++q) {
        int op, x1, y1, x2, y2; ll v;
        scanf("%d%d%d%d%d", &op, &x1, &y1, &x2, &y2);
        if (op <= 2) scanf("%lld", &v);
        if (op == 1) {
            for (int i = x1; i <= x2; ++i) st.add((i-1)*C+y1, (i-1)*C+y2, v);
        } else if (op == 2) {
            for (int i = x1; i <= x2; ++i) st.set((i-1)*C+y1, (i-1)*C+y2, v);
        } else {
            ll sum = 0, mn = INF, mx = -INF;
            for (int i = x1; i <= x2; ++i) {
                Res r = st.ask((i-1)*C+y1, (i-1)*C+y2);
                sum += r.sum; mn = min(mn, r.mn); mx = max(mx, r.mx);
            }
            printf("%lld %lld %lld\n", sum, mn, mx);
        }
    }
}

複雜度分析

• 展平後數組長 N = R*C ≤ 10^6。
• 單次操作最多橫跨 20 行 → 20 次線段樹操作。
• 每次線段樹操作 O(log N)。
• 總時間 O(M * R * log N) ≤ 20000 * 20 * 20 ≈ 8×10^6，極快。
• 空間 O(N) 線段樹節點約 4M，可接受。

總結

「行數少」是突破口，將二維區間操作轉化為多次一維區間操作。線段樹需正確處理賦值標記優先級高於加法標記的覆蓋語義，PushDown 時先推賦值再推加法。此題是「區間加 + 區間賦值 + 區間查詢」線段樹的經典實戰。