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

HDU 4819 Mosaic：二維線段樹解決矩形區域最大最小值查詢與單點更新

編輯：C++ 入門

題目大意

給定一個 N×N 的矩陣，每個格子有一個值。需要處理 Q 次操作，每次操作給出座標 (x, y) 和邊長 L，要求輸出以 (x, y) 為中心、邊長為 L 的正方形區域內最大值與最小值之和的一半，並將該值更新到 (x, y) 位置。

核心思路：二維線段樹（樹套樹）

本題屬於經典的二維區間查詢（最大值/最小值）與單點更新問題。一維線段樹可輕鬆處理區間查詢與單點更新，二維情況下採用「樹套樹」結構：第一維線段樹的每個節點維護一棵第二維線段樹。

資料結構設計

nodey：第二維線段樹節點，記錄區間 [l, r] 的最大值 maxval 與最小值 minval。
nodex：第一維線段樹節點，包含區間 [l, r] 以及一棵第二維線段樹 y[N*4]。

關鍵操作

建樹

遞歸建立第一維線段樹，對每個第一維節點再遞歸建立第二維線段樹，初始值設為極大/極小值。時間複雜度 O(N² log² N)，相當於執行 N² 次單點更新。

查詢

先在第一維線段樹上找到覆蓋查詢 x 區間的節點集合，再在對應的第二維線段樹上查詢 y 區間的最大值與最小值，最後合併結果。

單點更新

更新 (x, y) 位置的值時，需先在第一維定位到葉子節點（對應 x），更新該葉子的第二維線段樹中 y 位置的值；然後回溯第一維，利用左右子樹的第二維信息向上更新所有包含 x 的第一維節點對應的第二維線段樹。

代碼實現要點

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define INF 2147483647
#define N 805
#define L(x) (x<<1)
#define R(x) ((x<<1)|1)
#define Mid(x,y) ((x+y)>>1)

struct NodeY { int l, r, minval, maxval; };
struct NodeX { int l, r; NodeY y[N*4]; } x[N*4];

int n, q, lx, ly, ll;

void initY(int l, int r, int i, int j) { ... }
void initX(int l, int r, int i) { ... }

int maxAns, minAns;
void queryY(int l, int r, int i, int j) { ... }
void queryX(int l, int r, int i) { ... }

void updateY(int l, int i, int j, int key) { ... }
void updateX(int l, int i, int key) { ... }

int main() {
    int t; scanf("%d", &t);
    for (int k=1; k<=t; k++) {
        scanf("%d", &n);
        initX(1, n, 1);
        for (int i=1; i<=n; i++)
            for (int j=1; j<=n; j++) {
                int tmp; scanf("%d", &tmp);
                ly = j; updateX(i, 1, tmp);
            }
        scanf("%d", &q);
        printf("Case #%d:\n", k);
        while (q--) {
            scanf("%d%d%d", &lx, &ly, &ll);
            maxAns = -INF; minAns = INF;
            queryX(max(1, lx-ll/2), min(n, lx+ll/2), 1);
            int tmp = (maxAns + minAns) / 2;
            printf("%d\n", tmp);
            updateX(lx, 1, tmp);
        }
    }
    return 0;
}