概要

一直線上に並んだ展望台から空を眺める際、周囲の山の高さによって決まる「空の広さ」を最大化する展望台を選ぶ問題です。山の高さが更新されるクエリと、特定の範囲内で最適な展望台を答えるクエリを処理します。

考察

1. 「空の広さ」の最大化を言い換える

展望台 \(p\) における空の広さは \(V_p = \frac{1}{1 + L_p + R_p}\) で定義されます。 この値を最大化するということは、分母にある \(L_p + R_p\)（左右の遮り度の合計）を最小化する ことと同義です。

2. 計算量の見積もり

制約を見ると、展望台の数 \(N\) およびクエリの数 \(Q\) はともに \(200\) 以下と非常に小さいです。 - 1つの展望台 \(p\) について \(L_p\) と \(R_p\) を計算するには、他のすべての展望台を調べる必要があるため \(O(N)\) かかります。 - すべての展望台（\(N\) 個）について \(L_p, R_p\) を計算すると \(O(N^2)\) かかります。 - クエリごとにこれを計算しても、全体の計算量は \(O(Q \times N^2)\) となります。

\(200^3 = 8,000,000\) 程度なので、この素朴なシミュレーションで十分に制限時間内に間に合うことが分かります。

3. 精度の問題（有理数の比較）

\(L_p\) や \(R_p\) は「高さ \(\div\) 距離」という形をしており、割り算が発生します。浮動小数点数（float）で計算すると、誤差によって正しい比較ができない可能性があるため、有理数（分数）のまま比較を行う必要があります。

2つの分数 \(\frac{n_1}{d_1}\) と \(\frac{n_2}{d_2}\) の大小比較は、分母を払った形で行います： $\(\frac{n_1}{d_1} < \frac{n_2}{d_2} \iff n_1 \times d_2 < n_2 \times d_1\)$ Pythonでは標準で多倍長整数が扱えるため、大きな値の掛け算になっても精度を失わずに比較可能です。

アルゴリズム

1. 更新クエリ（タイプ1）の処理:

   • 指定された展望台 \(x\) の山の高さ \(H_x\) を更新します。
   • その後、すべての展望台 \(p\) について \(L_p\) と \(R_p\) を再計算します（またはクエリごとにその場で計算しても構いません）。

2. 取得クエリ（タイプ2）の処理:

   • 範囲 \([a, b]\) 内の各展望台 \(p\) について、\(L_p + R_p\) を計算します。
   • \(L_p = \frac{best\_ln}{best\_ld}\)、\(R_p = \frac{best\_rn}{best\_rd}\) とすると、その和は： $\(L_p + R_p = \frac{best\_ln \times best\_rd + best\_rn \times best\_ld}{best\_ld \times best\_rd}\)$ となります。
   • この分数の値を、これまでの最小値（暫定ベスト）と通分して比較し、最小となる \(p\) を更新していきます。
   • 値が同じ場合は、問題文の指示通り番号 \(p\) が小さい方を優先します。

計算量

• 時間計算量: \(O(Q \times N^2)\)
  • 各クエリにおいて、全展望台の \(L_p, R_p\) を求めるのに \(O(N^2)\)、範囲内の最小値を探すのに \(O(N)\) かかります。
• 空間計算量: \(O(N)\)
  • 山の高さや計算した \(L_p, R_p\) を保持するために必要なメモリです。

実装のポイント

• 通分による比較: \(L_p\) や \(R_p\) を求める際も、和を比較する際も、常に a * d < c * b の形を使って比較を行います。

• 初期値の設定: \(L_p + R_p\) の最小値を探す際、最初の展望台 \(p=a\) の値を初期値とするか、十分に大きな分数（無限大の代わり）を初期値として設定します。

• 1-indexedへの対応: 問題文は展望台 \(1 \sim N\) です。配列のサイズを \(N+1\) にするなどして、添え字のずれに注意しましょう。

  ソースコード

import sys

# 問題の要件：
# 1. 展望台 p における「空の広さ」V_p = 1 / (1 + L_p + R_p) を最大化する。
#    これは、(L_p + R_p) を最小化することと同義である。
# 2. L_p = max_{1 <= l < p} (H_l / (p - l)), R_p = max_{p < r <= N} (H_r / (r - p))。
# 3. 山の高さ H_x が更新されるクエリと、範囲 [a, b] で V_p が最大の p を求めるクエリを処理する。
# 4. 制約 N, Q <= 200 より、全体の計算量が O(Q * N^2) のアルゴリズムで十分間に合う。
# 5. V_p の比較は厳密な有理数計算（多倍長整数による通分比較）で行う。

def solve():
    # 標準入力からすべてのデータを読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    Q = int(input_data[1])
    
    # 展望台の高さ H を保持（1-indexed）
    H = [0] * (N + 1)
    for i in range(1, N + 1):
        H[i] = int(input_data[1 + i])
        
    # 各展望台 p における L_p と R_p を (分子, 分母) の形で保持する
    L_num = [0] * (N + 1)
    L_den = [1] * (N + 1)
    R_num = [0] * (N + 1)
    R_den = [1] * (N + 1)
    
    # 全展望台の L_p, R_p を再計算する関数
    def update_all_LR():
        for p in range(1, N + 1):
            # 左方向の遮り度 L_p の計算
            best_ln, best_ld = 0, 1
            for l in range(1, p):
                curr_n, curr_d = H[l], p - l
                # 有理数の比較: curr_n / curr_d > best_ln / best_ld
                if curr_n * best_ld > best_ln * curr_d:
                    best_ln, best_ld = curr_n, curr_d
            L_num[p], L_den[p] = best_ln, best_ld
            
            # 右方向の遮り度 R_p の計算
            best_rn, best_rd = 0, 1
            for r in range(p + 1, N + 1):
                curr_n, curr_d = H[r], r - p
                # 有理数の比較: curr_n / curr_d > best_rn / best_rd
                if curr_n * best_rd > best_rn * curr_d:
                    best_rn, best_rd = curr_n, curr_d
            R_num[p], R_den[p] = best_rn, best_rd

    # 初期の L_p, R_p を計算
    update_all_LR()
    
    current_idx = 2 + N
    results = []
    for _ in range(Q):
        if current_idx >= len(input_data):
            break
        
        query_type = int(input_data[current_idx])
        if query_type == 1:
            # タイプ 1: 高さを更新
            x = int(input_data[current_idx + 1])
            h = int(input_data[current_idx + 2])
            H[x] = h
            # 高さが変わると全展望台の L_p, R_p が影響を受ける可能性があるため再計算
            update_all_LR()
            current_idx += 3
        elif query_type == 2:
            # タイプ 2: 範囲 [a, b] で (L_p + R_p) が最小の p を探索
            a = int(input_data[current_idx + 1])
            b = int(input_data[current_idx + 2])
            
            best_p = -1
            best_sum_num = -1
            best_sum_den = -1
            
            for p in range(a, b + 1):
                ln, ld = L_num[p], L_den[p]
                rn, rd = R_num[p], R_den[p]
                
                # (L_p + R_p) を通分して計算
                # L_p + R_p = (ln * rd + rn * ld) / (ld * rd)
                curr_sum_num = ln * rd + rn * ld
                curr_sum_den = ld * rd
                
                if best_p == -1:
                    best_sum_num = curr_sum_num
                    best_sum_den = curr_sum_den
                    best_p = p
                else:
                    # 有理数の比較: curr_sum_num / curr_sum_den < best_sum_num / best_sum_den
                    if curr_sum_num * best_sum_den < best_sum_num * curr_sum_den:
                        best_sum_num = curr_sum_num
                        best_sum_den = curr_sum_den
                        best_p = p
                    # 値が等しい場合は、番号が小さい方を優先するため、不等号は厳密な小なりを用いる
            
            results.append(str(best_p))
            current_idx += 3
            
    # タイプ 2 クエリの結果をまとめて出力
    if results:
        sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-thinking によって生成されました。