HDU 4456 Crowd：二維樹狀數組 + 離散化 + 45° 旋轉技巧

HDU 4456 Crowd：二維樹狀數組離散化解法

題目大意

N×N 網格，M 次操作：

1. 1 x y z：(x,y) 加 z。
2. 2 x y z：查詢曼哈頓距離 ≤ z 的點值總和。

核心技巧：座標旋轉 45°

曼哈頓距離圓菱形區域 → 旋轉後變為軸對齊矩形。
變換：u = x - y + N, v = x + y。
查詢範圍：u ∈ [x-y+z+N, x-y-z+N], v ∈ [x+y-z, x+y+z] → 矩形區間和。

離散化二維 BIT

• 直接開 N×N 陣列會 MLE（N≤40000）。
• 預掃描所有操作，收集會被更新的 (u,v) 座標（含 BIT 內部索引 i += lowbit(i) 產生的所有點）。
• 將所有 u*W + v 排序去重，映射為 1D 索引，fenwick 陣列大小 = 唯一座標數（約 4M log²N，可控）。

核心程式碼片段

// 座標轉換
int u = x - y + N;
int v = x + y;

// 離散化收集
for (int i = u; i <= W; i += lowbit(i))
    for (int j = v; j <= W; j += lowbit(j))
        H[E++] = i * W + j;

// BIT 更新/查詢使用 lower_bound 映射索引
void add(int u, int v, int val) {
    for (int i=u; i<=W; i+=lowbit(i))
        for (int j=v; j<=W; j+=lowbit(j))
            fenw[lower_bound(H+1, H+E, i*W+j)-H] += val;
}
int sum(int u, int v) { /* 同理映射累加 */ }

複雜度

• 預處理：O(M log²N)。
• 單次操作：O(log²N)。
• 空間：O(M log²N)，遠小於 N²。