概要

各展望台 \(p\) について「左右にある山がどれだけ視界を遮るか」を最大の傾き（高さ÷距離）で表し、\(V_p=\dfrac{1}{1+L_p+R_p}\) が最大になる展望台を区間クエリで答える問題です。高さ更新もあるため、都度 \(V_p\) を正確に比較して最良の番号を求めます。

考察

重要な観察 1：\(L_p, R_p\) は「最大の比（分数）」で決まる

左方向は $\(L_p=\max_{1\le l<p}\frac{H_l}{p-l}\)\( 右方向も同様です。つまり \)p$ から見て、左（右）にある各山が作る「視線の傾き」の最大値だけ分かればよいです。

例えば \(p=5\) のとき、左の \(l=2,4\) に対して - \(l=2\): \(\dfrac{H_2}{3}\) - \(l=4\): \(\dfrac{H_4}{1}\) を比べて大きい方が \(L_5\) になります。

重要な観察 2：\(V_p\) の大小比較は浮動小数では危険

\(V_p\) は有理数で、問題文も「厳密な値で比較」とあります。浮動小数（float）で比較すると、誤差で大小が逆転して WA になり得ます。

そこで、分数を 分子・分母の整数 として持ち、比較は $\(\frac{a}{b}>\frac{c}{d}\iff ad>cb\)$ のように 交差乗算で行います（オーバーフローが心配ですが、Python の整数は任意精度なので安全です）。

素朴でも間に合う理由

\(N,Q\le 200\) と小さいため、タイプ2クエリのたびに - 各 \(p\in[a,b]\) について \(L_p\) を \(O(N)\)、\(R_p\) を \(O(N)\) で計算 - その中で最大の \(V_p\) を探す という全探索でも十分間に合います（最大でも \(200 \times 200 \times 200\) 程度）。

アルゴリズム

1. ある \(p\) の \(L_p, R_p\) を分数で求める

• \(L_p\) を最大化する \(l\) を全探索し、分数 \(\dfrac{H_l}{p-l}\) の最大を取る
  比較は交差乗算で行う：
  • 現在の最大が \(\dfrac{Lnum}{Lden}\)
  • 新候補が \(\dfrac{num}{den}=\dfrac{H_l}{p-l}\)
  • num * Lden > Lnum * den なら更新
• \(R_p\) も同様に求める（右側の \(r\) を全探索）

2. \(V_p=\dfrac{1}{1+L_p+R_p}\) を分数で作る

\(L=\dfrac{Lnum}{Lden},\; R=\dfrac{Rnum}{Rden}\) とすると $\(1+L+R=1+\frac{Lnum}{Lden}+\frac{Rnum}{Rden} =\frac{Lden\cdot Rden + Lnum\cdot Rden + Rnum\cdot Lden}{Lden\cdot Rden}\)\( よって \)\(V_p=\frac{1}{1+L+R} =\frac{Lden\cdot Rden}{Lden\cdot Rden + Lnum\cdot Rden + Rnum\cdot Lden}\)\( コードでは - `Vnum = Lden * Rden` - `Vden = Vnum + Lnum * Rden + Rnum * Lden` として \)(Vnum, Vden)$ を返します。

3. タイプ2クエリ（区間内で最大の \(V_p\)）

• \(p=a..b\) を順に走査し、各 \(V_p\) を計算
• 最大の分数を交差乗算で比較
  \(\dfrac{x}{y}\) と \(\dfrac{u}{v}\) の比較は x*v と u*y
• 同値なら「番号が小さい方」を採用（今回は左から走査しているので、更新条件に p < best_p を入れて厳密に処理）

4. タイプ1クエリ（更新）

H[x] = h とするだけ。次のタイプ2では新しい配列で再計算します。

計算量

• 時間計算量:
  タイプ2 1回につき、区間長を最大 \(N\) とすると各 \(p\) で \(L,R\) 計算が \(O(N)\) なので \(O(N^2)\)。
  全体では最大で \(O(QN^2)\)（\(200\cdot 200^2=8\times 10^6\) 程度）。
• 空間計算量: \(O(N)\)（高さ配列と定数個の変数のみ）

実装のポイント

• 分数は必ず整数の組（分子・分母）で持つ：float を使わない。

• 比較は交差乗算：a/b > c/d は a*d > c*b。

• \(p=1\) のとき左が無いので \(L_p=0\)、\(p=N\) のとき右が無いので \(R_p=0\)。コードでは初期値を (0,1) にして自然に処理しています。

• 同率最大のときは 番号が小さい方。比較で同値の場合の処理を忘れないようにします。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    H = [0] + list(map(int, input().split()))

    def compute_V(p: int):
        # L_p
        Lnum, Lden = 0, 1
        for l in range(1, p):
            num = H[l]
            den = p - l
            if num * Lden > Lnum * den:
                Lnum, Lden = num, den

        # R_p
        Rnum, Rden = 0, 1
        for r in range(p + 1, N + 1):
            num = H[r]
            den = r - p
            if num * Rden > Rnum * den:
                Rnum, Rden = num, den

        # V_p = 1 / (1 + L + R) where L=Lnum/Lden, R=Rnum/Rden
        Vnum = Lden * Rden
        Vden = Vnum + Lnum * Rden + Rnum * Lden
        return Vnum, Vden

    out = []
    for _ in range(Q):
        q = input().split()
        t = int(q[0])
        if t == 1:
            x = int(q[1])
            h = int(q[2])
            H[x] = h
        else:
            a = int(q[1])
            b = int(q[2])

            best_p = a
            best_num, best_den = compute_V(a)

            for p in range(a + 1, b + 1):
                num, den = compute_V(p)
                left = num * best_den
                right = best_num * den
                if left > right or (left == right and p < best_p):
                    best_p = p
                    best_num, best_den = num, den

            out.append(str(best_p))

    print("\n".join(out))

if __name__ == "__main__":
    main()

---

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