Overview

By applying a coordinate transformation to each shop \((x,y)\) so that we work in the \((u,v)=(x+y,\ x-y)\) plane, the “diamond-shaped region” of Manhattan distance becomes a “rectangle aligned with the axes.”
By efficiently handling the weighted point counting within this rectangle using a 2D prefix sum, we can answer all queries efficiently.

Key Observation

The crucial observation is the following equivalence.

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

Under the substitution
[ u=x+y,\quad v=x-y,\quad u_c=p+q,\quad v_c=p-q ]

this becomes equivalent to

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

In other words, the condition reduces to a “rectangle containment check”:

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

---

A naive approach of iterating over all shops for each candidate has a time complexity of \(O(NM)\).
At worst, this would require around \(10^5 \times 10^5 = 10^{10}\) checks, which is clearly too slow.

Looking at the constraints, the original coordinates satisfy \(0\le x,y\le 1000\), so:

• \(u=x+y\) ranges from \(0\) to \(2000\)
• \(v=x-y\) ranges from \(-1000\) to \(1000\)

The range of possible values is small (both are around 2000 at most).
By exploiting this “small coordinate range” property, we can aggregate sales onto a 2D grid and build a 2D prefix sum.
Then each query can compute the rectangle sum in \(O(1)\).

Algorithm

1. Coordinate transformation and point aggregation

   • For each shop \((x,y,c)\), compute: [ u=x+y,\quad v=x-y ]
   • Since \(v\) can be negative, add an offset (\(+1000\)) for array indexing.
   • If multiple shops share the same \((u,v)\), simply add their sales \(c\) together.

2. Build the 2D prefix sum

   • From grid[u][v], construct ps[u][v] (the prefix sum from the top-left corner).
   • This allows any rectangle sum to be computed via inclusion-exclusion.

3. Process each query

   • Transform the candidate \((p,q,k)\) as: [ u_c=p+q,\quad v_c=p-q ]
   • The corresponding rectangle is: [ [u_c-k,\ u_c+k]\times[v_c-k,\ v_c+k] ]
   • Clamp the rectangle to the grid boundaries.
   • If the range is completely outside the grid, the answer is 0.
   • Otherwise, retrieve the rectangle sum from the prefix sum in \(O(1)\) and output it.

Complexity

• Time complexity: \(O(N + U\!V + M)\)
  Here \(U=2001,\ V=2001\), so effectively around \(O(N+M+4\times10^6)\).
• Space complexity: \(O(U\!V)\) (with a constant factor for storing both grid and ps)

Implementation Notes

• Since \(v=x-y\) can be negative, an offset (VOFF=1000 in the code) is essential.

• In the prefix sum array, treating the column direction as 1-based by storing at v+1 makes the inclusion-exclusion formula easier to write.

• For the query rectangle, it is safest to:

  • First check “is it completely outside the grid?”
  • Then clamp the boundaries.

• The case where multiple shops share the same point is naturally handled by += c.

  Source Code

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()

---

This editorial was generated by gpt-5.3-codex.