概要

この問題では、一直線上に並んだ展望台から景色を見る際に、どの展望台が最も広い「空の広さ」を持つのかを求めるクエリに答える必要があります。また、途中で山の高さが変更されるイベントも処理します。

考察

まず、各展望台 \(p\) における「空の広さ」\(V_p\) は以下のように求められます：

• 左方向の最大傾き \(L_p = \max_{l < p} \frac{H_l}{p - l}\)
• 右方向の最大傾き \(R_p = \max_{r > p} \frac{H_r}{r - p}\)
• 空の広さ \(V_p = \frac{1}{1 + L_p + R_p}\)

傾きの比較や加算を正確に行うために、Python の fractions.Fraction を使うことで誤差なく計算できます。

素朴な方法では、クエリ2に対して範囲内の各展望台について毎回 \(L_p\) と \(R_p\) を全探索で計算するため、最悪ケースで \(O(N^2)\) の計算が必要になります。制約 \(N, Q \leq 200\) なので、最大で \(200 \times 200 \times 200 = 8,000,000\) 回程度の計算となり、間に合います。

したがって、この問題では全探索による単純な実装でも十分高速に動作します。

アルゴリズム

1. 各タイプ2のクエリに対して、区間 \([a, b]\) 内の各展望台 \(p\) について：
   • \(L_p\) を \(l = 1\) から \(p-1\) まで見て最大の傾きを求める
   • \(R_p\) を \(r = p+1\) から \(N\) まで見て最大の傾きを求める
   • \(V_p = \frac{1}{1 + L_p + R_p}\) を計算
2. 最大の \(V_p\) を持つ中で最小の \(p\) を選ぶ
3. タイプ1のクエリでは、単に配列 \(H\) の値を更新するだけ

すべての計算は Fraction を使って正確に行い、大小比較も正確に行います。

計算量

• 時間計算量: \(O(Q \cdot N^2)\)
  各タイプ2クエリで区間内の各点について、左右の傾きを計算するのに最大 \(O(N)\) かかるため、全体で \(O(Q \cdot N^2)\)
• 空間計算量: \(O(N)\)
  高さを保存する配列 \(H\) といくつかの変数のみ使用

実装のポイント

• 浮動小数点数を使うと精度エラーの原因になるため、fractions.Fraction を使って厳密に計算する

• インデックスが1始まりであることに注意（配列を1-indexedで扱う）

• タイプ2のクエリで最大値が同じ場合、最も番号の小さい展望台を選ぶ必要がある点に注意

  ソースコード

import sys
from fractions import Fraction

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx])
    idx += 1
    Q = int(data[idx])
    idx += 1
    
    H = [0] * (N+1)
    for i in range(1, N+1):
        H[i] = int(data[idx])
        idx += 1
    
    def compute_L_R(p):
        L = Fraction(0)
        if p > 1:
            for l in range(1, p):
                slope = Fraction(H[l], p - l)
                if slope > L:
                    L = slope
        R = Fraction(0)
        if p < N:
            for r in range(p+1, N+1):
                slope = Fraction(H[r], r - p)
                if slope > R:
                    R = slope
        return L, R
    
    def compute_V(p):
        L, R = compute_L_R(p)
        denom = Fraction(1) + L + R
        return Fraction(1, denom)
    
    results = []
    for _ in range(Q):
        t = int(data[idx])
        idx += 1
        if t == 1:
            x = int(data[idx])
            idx += 1
            h = int(data[idx])
            idx += 1
            H[x] = h
        else:
            a = int(data[idx])
            idx += 1
            b = int(data[idx])
            idx += 1
            max_V = Fraction(-1)
            best_p = -1
            for p in range(a, b+1):
                V_p = compute_V(p)
                if V_p > max_V:
                    max_V = V_p
                    best_p = p
            results.append(best_p)
    
    print('\n'.join(map(str, results)))

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。