概要

この問題は、一直線上に並んだ展望台の山の高さが変化する中で、各展望台からの「空の広さ」を計算し、指定された範囲内で最も空が広く見える展望台を見つける問題です。

考察

問題の核心は、各展望台 \(p\) について左方向と右方向の「遮り度」\(L_p\) と \(R_p\) を計算し、そこから空の広さ \(V_p = \frac{1}{1 + L_p + R_p}\) を求めることです。遮り度は、他の展望台の山が距離に対する高さの比 \(\frac{H_i}{|p-i|}\) で視界を遮る度合いを表し、その最大値を取ります。

制約条件が \(N, Q \leq 200\) と小さいため、各クエリに対して素朴に全ての展望台について \(L_p\) と \(R_p\) を計算しても十分に実行可能です。より効率的なアルゴリズム（例: 凸包テクニック）を考える必要はなく、シンプルな二重ループで解くことができます。

アルゴリズム

1. 山の高さの配列 \(H\) を保持します。
2. 各クエリを順に処理します：
   • タイプ1（更新）：\(H[x]\) を新しい値 \(h\) に更新します。
   • タイプ2（質問）：範囲 \([a, b]\) 内の各展望台 \(p\) について以下を計算します：
     • \(L_p\): \(p\) より左にある全ての展望台 \(l\) について \(\frac{H_l}{p-l}\) の最大値を計算します（\(p=1\) の場合は0）。
     • \(R_p\): \(p\) より右にある全ての展望台 \(r\) について \(\frac{H_r}{r-p}\) の最大値を計算します（\(p=N\) の場合は0）。
     • \(V_p = \frac{1}{1 + L_p + R_p}\) を計算します。
3. \(V_p\) が最大となる \(p\) を見つけます（同値の場合は最も小さい番号を選びます）。

計算量

• 時間計算量: \(O(Q \cdot N^2)\)
  • タイプ2のクエリ1つあたり \(O(N^2)\) の計算が必要です（\(p\) ごとに左右の全展望台をチェック）。
  • \(N, Q\) の最大値が200なので、最大計算量は \(200 \cdot 200^2 = 8,000,000\) 回となり、十分高速です。
• 空間計算量: \(O(N)\)
  • 山の高さを格納する配列のサイズが \(N\) です。

実装のポイント

• 浮動小数点数の比較では、誤差を考慮して abs(Vp - best_v) < 1e-12 のような許容誤差を設けると安全です（ただし、この問題では整数の除算のみなので厳密な有理数比較が可能ですが、実装の簡便さから浮動小数点数を使用しています）。

• 配列のインデックスは1-indexedで扱うため、配列のサイズを \(n+1\) とし、インデックス1からnまでを使用します。

• 各クエリで山の高さが更新されるため、常に最新の \(H\) を使って計算します。

  ソースコード

def main():
    import sys
    data = sys.stdin.read().split()
    it = iter(data)
    n = int(next(it))
    q = int(next(it))
    H = [0] * (n + 1)
    for i in range(1, n + 1):
        H[i] = int(next(it))
    
    output_lines = []
    
    for _ in range(q):
        t = next(it)
        if t == '1':
            x = int(next(it))
            h = int(next(it))
            H[x] = h
        else:
            a = int(next(it))
            b = int(next(it))
            best_p = -1
            best_v = -1.0
            
            for p in range(a, b + 1):
                Lp = 0.0
                if p > 1:
                    for l in range(1, p):
                        ratio = H[l] / (p - l)
                        if ratio > Lp:
                            Lp = ratio
                
                Rp = 0.0
                if p < n:
                    for r in range(p + 1, n + 1):
                        ratio = H[r] / (r - p)
                        if ratio > Rp:
                            Rp = ratio
                
                Vp = 1.0 / (1.0 + Lp + Rp)
                
                if Vp > best_v or (abs(Vp - best_v) < 1e-12 and p < best_p):
                    best_v = Vp
                    best_p = p
            
            output_lines.append(str(best_p))
    
    print("\n".join(output_lines))

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。