概要

道路上の各整数座標における信号強度 \(f(p)\) を効率的に前計算し、複数の区間最大値クエリに高速に答える問題です。

考察

素朴なアプローチの問題点

各クエリごとに区間内のすべての整数座標 \(p\) について \(f(p)\) を計算すると、1回の \(f(p)\) の計算に \(O(N)\)、座標の範囲が最大 \(2 \times 10^5\)、クエリが \(Q\) 個あるため、最悪 \(O(Q \times N \times 2 \times 10^5)\) となり到底間に合いません。

重要な気づき

気づき1: 各電波塔の寄与は「テント関数」である

電波塔 \(i\) が座標 \(p\) に届ける信号強度は \(\max(0, B_i - |p - X_i|)\) です。これは \(X_i\) を頂点（高さ \(B_i\)）とする三角形（テント型）の関数です。

例えば \(X_i = 5, B_i = 3\) の場合：

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

座標 \(3\) から \(7\) の範囲で値を持ち、\(5\) で最大値 \(3\) をとります。

気づき2: テント関数の和は二階差分配列で高速に計算できる

テント関数は区分線形関数です。傾きが \(+1 \to -1 \to 0\) と変化するため、二階差分（差分の差分）を使えば、全塔の寄与を重ね合わせた \(f(p)\) を全座標で \(O(N + \text{座標範囲})\) で計算できます。

気づき3: 区間最大値クエリはSparse Tableで \(O(1)\) 回答できる

\(f(p)\) の値が全座標で求まれば、あとは「配列の区間最大値」を繰り返し求める問題になります。これは Sparse Table を使えば前処理 \(O(M \log M)\)、クエリ \(O(1)\) で処理できます。

アルゴリズム

ステップ1: 二階差分配列で \(f(p)\) を計算

各電波塔（座標 \(X\)、出力 \(B\)）のテント関数の傾き変化を考えます。

• 座標 \(X - B + 1\) から傾き \(+1\) が始まる → 二階差分に \(+1\)
• 座標 \(X + 1\) で傾きが \(+1\) から \(-1\) に変わる → 二階差分に \(-2\)
• 座標 \(X + B + 1\) で傾き \(-1\) が終わる → 二階差分に \(+1\)

これを全電波塔について加算した後、累積和を2回取ることで \(f(p)\) が得られます。

• 1回目の累積和 → 傾き（一階差分）が復元される
• 2回目の累積和 → \(f(p)\) 自体が復元される

\(X - B\) が負になる場合があるため、配列にオフセットを加えて対処します。

ステップ2: Sparse Table の構築

\(f(0), f(1), \ldots, f(200000)\) の配列に対して Sparse Table を構築します。

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

を前計算しておきます。

ステップ3: クエリ応答

区間 \([L, R]\) に対して、長さ \(\ell = R - L + 1\) とし、\(k = \lfloor \log_2 \ell \rfloor\) として：

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

これにより \(O(1)\) で区間最大値が求まります。

計算量

• 時間計算量: \(O(N + M \log M + Q)\)（\(M = 2 \times 10^5\) は座標範囲）
  • 二階差分配列の構築: \(O(N)\)
  • 累積和2回で \(f(p)\) の計算: \(O(M)\)
  • Sparse Table の構築: \(O(M \log M)\)
  • 各クエリの応答: \(O(1)\)
• 空間計算量: \(O(M \log M)\)（Sparse Table の格納）

実装のポイント

• オフセットの導入: \(X - B + 1\) が負になりうるため、二階差分配列のインデックスに十分大きなオフセット（\(200001\)）を加えて非負にしています。

• 累積和のスタート地点: オフセットを使っているため、累積和は \(p = -200000\) 付近から開始し、\(p = 0\) ～ \(200000\) の部分だけ結果を取り出します。

• Sparse Table の \(k\) の計算: int(log2(length)) で浮動小数点誤差が起きる可能性があるため、bit_length() を使う方が安全です。コード中では log2 の結果を確認して補正しています。

• 差分配列のサイズ: \(X + B + 1\) が最大 \(400001\) 程度になるため、配列サイズに余裕を持たせています。

  ソースコード

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

---

この解説は claude4.6opus-thinking によって生成されました。