題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 awc0065_d Total Sales Within Delivery Range

Problem Statement

題目簡述

平面上有 $N$ 個店鋪，第 $i$ 個店鋪位於 $(X_i, Y_i)$ 座標並有一個銷售額 $C_i$ 。
接著有 $M$ 組查詢，對於第 $j$ 個查詢，給定一個配送中心座標 $(P_j, Q_j)$ 與可配送距離 $K_j$ ，求所有曼哈頓距離不超過該距離的店鋪銷售額總和。

Constraints

約束條件

$1 \leq N, M \leq 10^5$
$N + M \leq 1.5 \times 10^5$
$0 \leq X_i, Y_i, P_j, Q_j \leq 1000$
$1 \leq C_i \leq 10^4$
$0 \leq K_j \leq 2000$
所有輸入皆為整數

思路：座標旋轉 + 二維前綴和

從查詢形狀觀察

每次查詢要找的是「到目前位置的曼哈頓距離不超過某個距離」的所有店鋪。直接在原座標系看，這個範圍是一個菱形；如果每次都掃過所有店鋪，就會在多筆查詢時變得太慢。

Question

有沒有辦法把菱形範圍變成比較容易快速求和的形狀？

座標旋轉：曼哈頓距離轉切比雪夫距離

曼哈頓距離有一個常見轉換：將每個點的座標從 $(x, y)$ 轉換成 $(u, v)$ ，其中 $u = x + y$ 、 $v = x - y$ 。在這個新的座標系裡，曼哈頓距離不超過 $k$ 的範圍會變成一個軸對齊的矩形。

Tip

若兩點的曼哈頓距離不超過 $k$ ，等價於旋轉座標後，兩個新座標方向上的差距都不超過 $k$ 。

也就是說，查詢範圍可以從「原座標中的菱形」變成「新座標中的矩形」，而求矩形區間和的問題可以用二維前綴和解決。

實作上的細節

由於 $0 \leq X_i, Y_i, P_j, Q_j \leq 1000$ ，變換後的座標 $u \in [0, 2000]$ 、 $v \in [-1000, 1000]$ 。為了避免負數索引，可以將 $v$ 的範圍平移，使其變成 $[0, 2000]$ 。

為了方便計算二維前綴和，將原本的 $[0, 2000]$ 再調整為 $[1, 2001]$ ，這樣在計算前綴和時就不需要特別處理邊界問題。

複雜度分析

時間複雜度： $\mathcal{O}(V^2 + N + M)$ ，其中 $V=2000$ 為旋轉後座標範圍上限。
空間複雜度： $\mathcal{O}(V^2)$

Code

SHIFT = int(1e3)
MAX_V = int(2e3)


def main():
    n, m = map(int, input().split())

    # 曼哈頓距離透過旋轉座標轉成矩形範圍求和
    grid = [[0] * (MAX_V + 2) for _ in range(MAX_V + 2)]
    for _ in range(n):
        x, y, c = map(int, input().split())
        u = x + y
        v = x - y + SHIFT
        grid[u + 1][v + 1] += c

    for i in range(1, MAX_V + 2):
        for j in range(1, MAX_V + 2):
            grid[i][j] += grid[i - 1][j] + grid[i][j - 1] - grid[i - 1][j - 1]

    ans = []
    for _ in range(m):
        x, y, k = map(int, input().split())
        u, v = x + y, x - y + SHIFT

        u1 = max(u - k, 0) + 1
        v1 = max(v - k, 0) + 1
        u2 = min(u + k, MAX_V) + 1
        v2 = min(v + k, MAX_V) + 1

        ans.append(
            grid[u2][v2] - grid[u1 - 1][v2] - grid[u2][v1 - 1] + grid[u1 - 1][v1 - 1]
        )

    print(*ans, sep="\n")


if __name__ == "__main__":
    main()