概要

各電波塔の「三角形状」の寄与をすべて足し合わせて \(f(p)\) を全座標で高速に前計算し、各クエリ区間の最大値をセグメント木で答えます。

考察

電波塔 \(i\) の寄与は $\(g_i(p)=\max(0, B_i-|p-X_i|)\)\( で、これは座標 \)X_i\( を頂点（高さ \)B_i$）とする左右対称の三角形になります。

例えば \((X,B)=(5,3)\) なら、届く範囲は \(p\in[2,8]\) で、 - 左側 \(p\in[2,4]\) は \(g(p)=p+(3-5)=p-2\)（1ずつ増える） - 右側 \(p\in[5,8]\) は \(g(p)=-p+(3+5)=-p+8\)（1ずつ減る） です。

ここで重要なのは、各塔の寄与は区間ごとに一次関数（\(ap+c\)） だという点です。よって全体の和 \(f(p)\) も、各 \(p\) で $\(f(p)=A(p)\,p + C(p)\)\( という形（\)A(p),C(p)\( はその \)p$ で有効な一次関数の係数の総和）で計算できます。

素朴に各クエリ \([L,R]\) で全点を調べると、最悪で \(Q\cdot (R-L)\) が巨大（最大 \(10^5\cdot 2\cdot 10^5\)）になり TLE します。
そこで、 1. \(p=0..200000\) の全ての \(f(p)\) を \(O(N+MAX)\) で作る 2. 区間最大をデータ構造で高速に答える（\(O(\log MAX)\)） という方針にします。

アルゴリズム

座標の最大値を \(MAX=200000\) とします（問題の制約より）。

1) 各電波塔の寄与を「区間への一次関数加算」に分解

塔 \((x,b)\) の寄与は次の2区間に分かれます（整数座標のみ考える）：

• 左側：\(p \in [x-b, x-1]\)
  $\(g(p)=b-(x-p)=p+(b-x) \quad(\text{傾き } +1,\ 切片\ b-x)\)$

• 右側：\(p \in [x, x+b]\)
  $\(g(p)=b-(p-x)=-p+(b+x) \quad(\text{傾き } -1,\ 切片\ b+x)\)$

範囲外（\(p<0\) や \(p>MAX\)）はクランプして無視します。

2) 差分配列で「区間に傾き・切片を足す」を高速化

「区間 \([L,R]\) に一次関数 \(ap+c\) を足す」をたくさん行いたいので、 - 傾き用差分 diffA - 切片用差分 diffC を用意し、区間加算を - diffA[L] += a, diffA[R+1] -= a - diffC[L] += c, diffC[R+1] -= c で表します。

全塔の更新後、\(p=0..MAX\) を左から走査して累積和を取ると、その点での - \(A(p)\)（傾き合計） - \(C(p)\)（切片合計） が分かり、最後に $\(f(p)=A(p)\cdot p + C(p)\)$ で求まります。

3) セグメント木で区間最大クエリ

\( f(0..MAX)\) ができたら、配列 \(f\) 上の 区間最大値 を \(Q\) 回答える問題になります。
セグメント木（最大値）を構築して、各クエリ \([L,R]\) を \(O(\log MAX)\) で処理します。

計算量

• 時間計算量:
  前計算（差分更新）\(O(N)\)、累積と \(f\) 作成 \(O(MAX)\)、セグ木構築 \(O(MAX)\)、クエリ \(O(Q\log MAX)\)
  よって全体で \(O(N + MAX + Q\log MAX)\)
• 空間計算量:
  差分配列・\(f\)・セグ木で \(O(MAX)\)

（ここで \(MAX=200000\) は定数なので十分高速です。）

実装のポイント

• 左側区間は \([x-b, x-1]\)、右側区間は \([x, x+b]\) とし、\(p=x\) を右側に含めることで \(g(x)=b\) を正しく作ります。

• 区間端は必ず \([0,MAX]\) にクランプします（max(0, ...), min(MAX, ...)）。

• diff は R+1 に触れるので長さを MAX+3 程度にしておくと安全です。

• 値が大きくなり得るため（\(N\) 個が足し合わさる）、array('q') などの 64bit 整数で保持します。

  ソースコード

import sys
from array import array

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = 0
    N = data[it]; Q = data[it + 1]; it += 2

    MAX = 200000
    diffA = [0] * (MAX + 3)  # slope
    diffC = [0] * (MAX + 3)  # intercept

    def range_add(L, R, a, c):
        if L > R:
            return
        diffA[L] += a
        diffA[R + 1] -= a
        diffC[L] += c
        diffC[R + 1] -= c

    for _ in range(N):
        x = data[it]; b = data[it + 1]; it += 2

        # left: p in [x-b, x-1], g(p) = p + (b - x)
        L = max(0, x - b)
        R = min(MAX, x - 1)
        range_add(L, R, 1, b - x)

        # right: p in [x, x+b], g(p) = -p + (b + x)
        L = max(0, x)
        R = min(MAX, x + b)
        range_add(L, R, -1, b + x)

    f = array('q', [0]) * (MAX + 1)
    a = 0
    c = 0
    for p in range(MAX + 1):
        a += diffA[p]
        c += diffC[p]
        f[p] = a * p + c

    n = 1
    m = MAX + 1
    while n < m:
        n <<= 1

    NEG_INF = -(1 << 60)
    seg = array('q', [NEG_INF]) * (2 * n)
    seg[n:n + m] = f
    for i in range(n - 1, 0, -1):
        left = seg[i * 2]
        right = seg[i * 2 + 1]
        seg[i] = left if left >= right else right

    def range_max(l, r):
        l += n
        r += n + 1
        res = NEG_INF
        while l < r:
            if l & 1:
                v = seg[l]
                if v > res:
                    res = v
                l += 1
            if r & 1:
                r -= 1
                v = seg[r]
                if v > res:
                    res = v
            l >>= 1
            r >>= 1
        return res

    out = []
    for _ in range(Q):
        L = data[it]; R = data[it + 1]; it += 2
        out.append(str(range_max(L, R)))

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

if __name__ == "__main__":
    main()

---

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