概要

マンハッタン距離で表されるひし形の範囲を、座標変換 \(u=x+y,\ v=x-y\) によって長方形に変換し、2次元累積和で各クエリを高速に答える問題です。

考察

各候補ごとに全店舗を調べると、\(M\) 個の候補それぞれに対して \(N\) 軒の店舗を確認することになります。
この方法の計算量は \(O(NM)\) で、最大では

\[10^5 \times 10^5 = 10^{10}\]

となり、到底間に合いません。

では、どう高速化するかを考えます。

1. マンハッタン距離の領域はそのままだと扱いにくい

条件は

\[|X_i-P_j|+|Y_i-Q_j| \le K_j\]

です。
これは平面上では「ひし形」の領域になります。

ひし形に含まれる点の合計をそのまま高速に求めるのは少し面倒です。
そこで、座標を回転させるような変換を使います。

2. 座標変換 \(u=x+y,\ v=x-y\) を使う

各店舗の座標 \((x,y)\) を

\[u=x+y,\quad v=x-y\]

に変換します。

このとき、拠点 \((p,q)\) に対する差を

\[a=x-p,\quad b=y-q\]

とすると、条件は

\[|a|+|b| \le K\]

です。

ここで次の性質が成り立ちます。

\[|a|+|b| = \max(|a+b|,\ |a-b|)\]

したがって

\[|x-p|+|y-q| \le K\]

は

\[| (x+y) - (p+q) | \le K \quad \text{かつ} \quad | (x-y) - (p-q) | \le K\]

と同値です。

つまり、\((u,v)\) 平面では

\[u \in [u_0-K,\ u_0+K],\quad v \in [v_0-K,\ v_0+K]\]

という軸に平行な長方形になります。

ひし形が長方形に変わるので、2次元累積和が使えるようになります。

---

3. 座標範囲が小さいのが重要

制約を見ると

• \(0 \le X_i,Y_i \le 1000\)
• よって \(u=x+y\) は \(0\) から \(2000\)
• \(v=x-y\) は \(-1000\) から \(1000\)

です。

\(v\) は負になるので、配列で扱いやすいように

\[v' = x-y+1000\]

とずらします。
これで \(v'\) も \(0\) から \(2000\) に収まります。

つまり、必要なグリッドの大きさは \(2001 \times 2001\) 程度です。
このサイズなら、2次元累積和を前計算しても十分現実的です。

アルゴリズム

1. 変換後のグリッドを作る

各店舗 \((x,y,c)\) について

• \(u=x+y\)
• \(v=x-y+1000\)

を計算し、グリッド grid[u][v] に売上 \(c\) を加算します。
同じ座標に複数店舗があっても、単に加算すればよいです。

---

2. 2次元累積和を作る

grid[i][j] を、「左上から \((i,j)\) までの売上合計」を持つようにします。

これにより、長方形

\[[u_1,u_2] \times [v_1,v_2]\]

の合計は

\[S(u_2,v_2)-S(u_1-1,v_2)-S(u_2,v_1-1)+S(u_1-1,v_1-1)\]

で求められます。

実装では境界処理を簡単にするため、配列を 1-indexed 風にしてあります。

---

3. 各クエリを長方形和に変換する

候補 \((p,q,k)\) に対して

• \(u_0=p+q\)
• \(v_0=p-q+1000\)

を計算します。

配達可能な範囲は

\[u \in [u_0-k,\ u_0+k],\quad v \in [v_0-k,\ v_0+k]\]

です。
ただし配列範囲外に出ることがあるので、実際には

• \(u_1=\max(0,u_0-k)\)
• \(u_2=\min(2000,u_0+k)\)
• \(v_1=\max(0,v_0-k)\)
• \(v_2=\min(2000,v_0+k)\)

とします。

あとはこの長方形の累積和を取り出せば答えです。

---

4. 具体例

例えば拠点が \((2,3)\)、\(K=2\) だとします。

このとき

\[u_0 = 2+3 = 5,\quad v_0 = 2-3 = -1\]

です。
\(K=2\) なので、変換後の範囲は

\[u \in [3,7],\quad v \in [-3,1]\]

となります。
元の座標ではひし形ですが、変換後ではただの長方形です。

この長方形内にある店舗の売上合計を、2次元累積和で \(O(1)\) で求められます。

計算量

• 時間計算量: \(O(N + 2001^2 + M)\)
• 空間計算量: \(O(2001^2)\)

\(2001^2\) は定数に近い大きさなので、実質的には十分高速です。

実装のポイント

• \(v=x-y\) は負になるので、SHIFT = 1000 を足して非負にしています。

• 累積和を作りやすくするため、配列サイズを 2002 とし、0 行目・0 列目を番兵として使っています。

• クエリの長方形が範囲外にはみ出すことがあるので、0～2000 に切り詰める必要があります。

• 同じ座標に複数店舗がある場合も、そのまま加算すれば正しく扱えます。

• 実装では array('I') を使って、2次元配列のメモリ使用量を抑えています。

  ソースコード

import sys
from array import array

def main():
    input = sys.stdin.buffer.readline

    N, M = map(int, input().split())

    MAXC = 2000
    SHIFT = 1000
    DIM = MAXC + 2  # 0th row/col for prefix sums

    grid = [array('I', [0]) * DIM for _ in range(DIM)]

    for _ in range(N):
        x, y, c = map(int, input().split())
        u = x + y
        v = x - y + SHIFT
        grid[u + 1][v + 1] += c

    rng = range(1, DIM)
    for i in rng:
        row = grid[i]
        prev = grid[i - 1]
        s = 0
        for j in rng:
            s += row[j]
            row[j] = prev[j] + s

    out = []
    append = out.append
    g = grid

    for _ in range(M):
        p, q, k = map(int, input().split())
        u = p + q
        v = p - q + SHIFT

        u1 = u - k
        if u1 < 0:
            u1 = 0
        v1 = v - k
        if v1 < 0:
            v1 = 0
        u2 = u + k
        if u2 > MAXC:
            u2 = MAXC
        v2 = v + k
        if v2 > MAXC:
            v2 = MAXC

        row2 = g[u2 + 1]
        row1 = g[u1]
        ans = row2[v2 + 1] - row1[v2 + 1] - row2[v1] + row1[v1]
        append(str(ans))

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

---

この解説は gpt-5.4-high によって生成されました。