概要

各店舗 \((x,y)\) を座標変換して \((u,v)=(x+y,\ x-y)\) 平面で扱うと、マンハッタン距離の「ひし形領域」が「軸に平行な長方形領域」になります。
この長方形の重み付き点数え上げを 2 次元累積和で高速に処理することで、全クエリを効率よく解けます。

考察

重要な観察は次の等式です。

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

を、
[ u=x+y,\quad v=x-y,\quad u_c=p+q,\quad v_c=p-q ] に変換すると

[ \max\bigl(|u-u_c|,\ |v-v_c|\bigr)\le k ]

と同値になります。つまり条件は

[ u_c-k \le u \le u_c+k,\quad v_c-k \le v \le v_c+k ]

という「長方形内判定」になります。

---

素朴に各候補ごとに全店舗をなめると、計算量は \(O(NM)\)。
最大で \(10^5 \times 10^5 = 10^{10}\) 回程度の判定となり、当然間に合いません。

ここで制約を見ると、元の座標は \(0\le x,y\le 1000\) なので

• \(u=x+y\) は \(0\sim 2000\)
• \(v=x-y\) は \(-1000\sim 1000\)

と、取りうる値の範囲が小さいです（どちらも約 2000 程度）。
この「座標範囲が小さい」性質を使い、2D グリッドに売上を集約して 2 次元累積和を作れば、
各クエリは長方形和を \(O(1)\) で求められます。

アルゴリズム

1. 座標変換して点を集約

   • 各店舗 \((x,y,c)\) について [ u=x+y,\quad v=x-y ]
   • \(v\) は負になるので、配列添字用にオフセット（\(+1000\)）を足して管理。
   • 同じ \((u,v)\) に複数店舗があっても、売上 \(c\) を加算する。

2. 2 次元累積和を構築

   • grid[u][v] をもとに、ps[u][v]（左上からの累積）を作る。
   • これで任意長方形和が包除で取れる。

3. 各クエリ処理

   • 候補 \((p,q,k)\) を [ u_c=p+q,\quad v_c=p-q ] に変換。
   • 対応する長方形： [ [u_c-k,\ u_c+k]\times[v_c-k,\ v_c+k] ]
   • グリッド範囲外は切り詰め（clamp）。
   • 範囲が完全に外なら答えは 0。
   • そうでなければ累積和から長方形和を \(O(1)\) で取得して出力。

計算量

• 時間計算量: \(O(N + U\!V + M)\)
  ここで \(U=2001,\ V=2001\) なので実質 \(O(N+M+4\times10^6)\) 程度。
• 空間計算量: \(O(U\!V)\)（grid と ps を持つので定数倍あり）

実装のポイント

• \(v=x-y\) は負になるため、オフセット（コードでは VOFF=1000）が必須。

• 累積和配列で列方向を 1-based っぽく扱い、v+1 で保存すると包除が書きやすい。

• クエリ矩形は必ず

  • まず「完全に外か」を判定
  • その後に境界を切り詰める と安全です。

• 同一点に複数店舗があるケースは、+= c で自然に対応できています。

  ソースコード

import sys

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

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

    MAX_XY = 1000
    UMAX = 2000  # x+y range
    VMIN = -1000
    VMAX = 1000
    VOFF = 1000
    VSZ = VMAX - VMIN + 1  # 2001

    # grid in (u=x+y, v=x-y) space
    grid = [[0] * (VSZ + 1) for _ in range(UMAX + 1)]  # 1-based for prefix sum in v

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

    # 2D prefix sum over u (0..2000) and v (1..2001)
    ps = [[0] * (VSZ + 1) for _ in range(UMAX + 1)]
    # first row
    row_acc = 0
    for v in range(1, VSZ + 1):
        row_acc += grid[0][v]
        ps[0][v] = row_acc
    # remaining rows
    for u in range(1, UMAX + 1):
        row_acc = 0
        prev = ps[u - 1]
        cur = ps[u]
        gu = grid[u]
        for v in range(1, VSZ + 1):
            row_acc += gu[v]
            cur[v] = prev[v] + row_acc

    out = []
    for _ in range(M):
        p, q, k = map(int, input().split())
        uc = p + q
        vc = p - q

        u1 = uc - k
        u2 = uc + k
        v1 = vc - k
        v2 = vc + k

        if u2 < 0 or u1 > UMAX or v2 < VMIN or v1 > VMAX:
            out.append("0")
            continue

        if u1 < 0:
            u1 = 0
        if u2 > UMAX:
            u2 = UMAX
        if v1 < VMIN:
            v1 = VMIN
        if v2 > VMAX:
            v2 = VMAX

        # convert v to prefix indices (1..2001)
        lv = v1 + VOFF + 1
        rv = v2 + VOFF + 1

        res = ps[u2][rv]
        if u1 > 0:
            res -= ps[u1 - 1][rv]
        if lv > 1:
            res -= ps[u2][lv - 1]
            if u1 > 0:
                res += ps[u1 - 1][lv - 1]

        out.append(str(res))

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

if __name__ == "__main__":
    main()

---

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