Overview

This problem requires efficiently precomputing the signal strength \(f(p)\) at each integer coordinate on the road, then quickly answering multiple range maximum queries.

Analysis

Issues with the Naive Approach

If we compute \(f(p)\) for every integer coordinate \(p\) within the interval for each query, a single computation of \(f(p)\) takes \(O(N)\), the coordinate range is up to \(2 \times 10^5\), and there are \(Q\) queries, resulting in a worst case of \(O(Q \times N \times 2 \times 10^5)\), which is far too slow.

Key Observations

Observation 1: Each tower’s contribution is a “tent function”

The signal strength that tower \(i\) delivers to coordinate \(p\) is \(\max(0, B_i - |p - X_i|)\). This is a triangular (tent-shaped) function with its peak at \(X_i\) (height \(B_i\)).

For example, when \(X_i = 5, B_i = 3\):

    3
   /\
  /  \
 /    \
2  3  4  5  6  7  8
   1  2  3  2  1  0

It has nonzero values in the range from coordinate \(3\) to \(7\), reaching a maximum of \(3\) at \(5\).

Observation 2: The sum of tent functions can be computed efficiently using a second-order difference array

A tent function is a piecewise linear function. Since the slope changes as \(+1 \to -1 \to 0\), by using second-order differences (differences of differences), we can compute \(f(p)\) — the superposition of all towers’ contributions — across all coordinates in \(O(N + \text{coordinate range})\).

Observation 3: Range maximum queries can be answered in \(O(1)\) using a Sparse Table

Once the values of \(f(p)\) are computed for all coordinates, the problem reduces to repeatedly finding the maximum in a subarray. This can be handled with a Sparse Table: \(O(M \log M)\) preprocessing and \(O(1)\) per query.

Algorithm

Step 1: Compute \(f(p)\) using a second-order difference array

Consider the slope changes of the tent function for each tower (coordinate \(X\), power \(B\)):

• The slope \(+1\) begins at coordinate \(X - B + 1\) → add \(+1\) to the second-order difference array
• At coordinate \(X + 1\), the slope changes from \(+1\) to \(-1\) → add \(-2\) to the second-order difference array
• At coordinate \(X + B + 1\), the slope \(-1\) ends → add \(+1\) to the second-order difference array

After adding these for all towers, taking the prefix sum twice yields \(f(p)\):

• First prefix sum → restores the slope (first-order difference)
• Second prefix sum → restores \(f(p)\) itself

Since \(X - B\) can become negative, we handle this by adding an offset to the array indices.

Step 2: Build the Sparse Table

Build a Sparse Table over the array \(f(0), f(1), \ldots, f(200000)\).

Precompute:

\(\text{table}[k][i] = \max(f(i), f(i+1), \ldots, f(i + 2^k - 1))\)

Step 3: Answer Queries

For an interval \([L, R]\), let \(\ell = R - L + 1\) and \(k = \lfloor \log_2 \ell \rfloor\):

\[\text{answer} = \max(\text{table}[k][L],\ \text{table}[k][R - 2^k + 1])\]

This yields the range maximum in \(O(1)\).

Complexity

• Time complexity: \(O(N + M \log M + Q)\) (where \(M = 2 \times 10^5\) is the coordinate range)
  • Building the second-order difference array: \(O(N)\)
  • Computing \(f(p)\) with two prefix sums: \(O(M)\)
  • Building the Sparse Table: \(O(M \log M)\)
  • Answering each query: \(O(1)\)
• Space complexity: \(O(M \log M)\) (for storing the Sparse Table)

Implementation Notes

• Introducing an offset: Since \(X - B + 1\) can be negative, a sufficiently large offset (\(200001\)) is added to the second-order difference array indices to keep them non-negative.

• Starting point of the prefix sum: Because of the offset, the prefix sum starts from around \(p = -200000\), and we extract only the results for \(p = 0\) to \(200000\).

• Computing \(k\) for the Sparse Table: Using int(log2(length)) may cause floating-point errors, so using bit_length() is safer. In the code, the result of log2 is verified and corrected.

• Size of the difference array: Since \(X + B + 1\) can be up to approximately \(400001\), the array size is given sufficient margin.

  Source Code

import sys
from math import log2, ceil

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    Q = int(input_data[idx]); idx += 1
    
    MAX_COORD = 200001  # 0 to 200000
    
    # We need to compute f(p) for all integer p in [0, 200000]
    # f(p) = sum over i of max(0, B_i - |p - X_i|)
    # Each tower i contributes a "tent" function centered at X_i with height B_i
    # The tent goes from X_i - B_i + 1 to X_i + B_i - 1 (for integer coordinates where contribution > 0)
    
    # We can compute f using a difference array approach on the derivative.
    # The tent function for tower i: contribution at p is B_i - |p - X_i| when |p - X_i| < B_i
    # This is a piecewise linear function that increases by +1 per unit from X_i - B_i to X_i,
    # then decreases by -1 per unit from X_i to X_i + B_i.
    
    # Using second-order difference array:
    # For a tent of height B at center X:
    # The slope changes: +1 starting at X - B + 1, and -1 starting at X + 1 (slope goes from +1 to -1 = change of -2 at X+1... wait)
    
    # Let me think more carefully with first differences of f.
    # f'(p) = f(p) - f(p-1)
    # For one tower: g(p) = max(0, B - |p - X|)
    # g(p) - g(p-1): 
    #   When p <= X and p >= X - B + 1: g increases by 1 each step -> diff = +1
    #   When p > X and p <= X + B: g decreases by 1 each step -> diff = -1 (actually need to check)
    #   Wait, let me use difference of differences (second order).
    
    # Let's use the approach: accumulate using diff array twice.
    # For each tower at X with power B:
    # The contribution starts increasing at p = X - B + 1 (slope +1)
    # At p = X + 1, slope changes to -1 (delta of -2)
    # At p = X + B + 1, contribution returns to 0 (slope changes by +1, but we need to stop the -1)
    
    # Using second-order difference array d2:
    # d2[X - B + 1] += 1
    # d2[X + 1] -= 2
    # d2[X + B + 1] += 1
    
    SIZE = 400002  # enough room
    d2 = [0] * (SIZE + 2)
    
    for i in range(N):
        X = int(input_data[idx]); idx += 1
        B = int(input_data[idx]); idx += 1
        
        left = X - B + 1
        mid = X + 1
        right = X + B + 1
        
        # Clamp to valid range for accumulation
        if left < 0:
            # The slope starts before 0, so at p=0 we need to account for partial
            # We'll handle by letting indices go negative and then fix
            pass
        
        # We'll allow negative indices by offsetting
        OFFSET = 200001  # max B is 200000, max shift is 200000
        d2[left + OFFSET] += 1
        d2[mid + OFFSET] -= 2
        d2[right + OFFSET] += 1
    
    # First prefix sum -> first derivative
    # Second prefix sum -> f values
    # We need f(p) for p in [0, 200000]
    
    # Compute from the smallest possible index
    # smallest left = X - B + 1, min is 0 - 200000 + 1 = -199999
    # We need to sum from -199999 + OFFSET = 2 up to 200000 + OFFSET
    
    f_vals = [0] * (MAX_COORD)  # f_vals[p] = f(p) for p=0..200000
    
    slope = 0
    val = 0
    start = -200000  # safe lower bound
    for p in range(start, 200001):
        slope += d2[p + OFFSET]
        val += slope
        if 0 <= p <= 200000:
            f_vals[p] = val
    
    # Now build a sparse table for range max queries
    n = MAX_COORD  # 200001 elements
    LOG = max(1, n.bit_length())
    table = [f_vals[:]]
    for k in range(1, LOG):
        prev = table[k-1]
        length = 1 << k
        cur = [0] * (n - length + 1)
        half = 1 << (k-1)
        for i in range(len(cur)):
            cur[i] = max(prev[i], prev[i + half])
        table.append(cur)
    
    out = []
    for _ in range(Q):
        L = int(input_data[idx]); idx += 1
        R = int(input_data[idx]); idx += 1
        length = R - L + 1
        if length == 1:
            out.append(str(f_vals[L]))
        else:
            k = int(log2(length))
            if (1 << k) > length:
                k -= 1
            out.append(str(max(table[k][L], table[k][R - (1 << k) + 1])))
    
    sys.stdout.write('\n'.join(out) + '\n')

main()

---

This editorial was generated by claude4.6opus-thinking.