Overview

When viewing the sky from observation decks lined up in a straight line, the problem asks you to choose the observation deck that maximizes the “sky width,” which is determined by the heights of surrounding mountains. You need to process queries that update mountain heights and queries that find the optimal observation deck within a specific range.

Analysis

1. Rephrasing the Maximization of “Sky Width”

The sky width at observation deck \(p\) is defined as \(V_p = \frac{1}{1 + L_p + R_p}\). Maximizing this value is equivalent to minimizing \(L_p + R_p\) (the sum of left and right obstruction degrees) in the denominator.

2. Estimating Computational Complexity

Looking at the constraints, both the number of observation decks \(N\) and the number of queries \(Q\) are at most \(200\), which is very small. - Computing \(L_p\) and \(R_p\) for a single observation deck \(p\) requires examining all other observation decks, taking \(O(N)\). - Computing \(L_p, R_p\) for all \(N\) observation decks takes \(O(N^2)\). - Even if we compute this for each query, the total complexity is \(O(Q \times N^2)\).

Since \(200^3 = 8,000,000\), this naive simulation is sufficient to run within the time limit.

3. Precision Issues (Rational Number Comparison)

\(L_p\) and \(R_p\) have the form “height \(\div\) distance,” which involves division. Computing with floating-point numbers (float) may cause errors that prevent correct comparisons, so comparisons must be performed using rational numbers (fractions).

Comparing two fractions \(\frac{n_1}{d_1}\) and \(\frac{n_2}{d_2}\) is done by cross-multiplying to eliminate denominators: $\(\frac{n_1}{d_1} < \frac{n_2}{d_2} \iff n_1 \times d_2 < n_2 \times d_1\)$ Since Python natively supports arbitrary-precision integers, comparisons can be performed without losing precision even when multiplications involve large values.

Algorithm

1. Processing Update Queries (Type 1):

   • Update the mountain height \(H_x\) of the specified observation deck \(x\).
   • Afterward, recompute \(L_p\) and \(R_p\) for all observation decks \(p\) (or compute them on the fly for each query).

2. Processing Retrieval Queries (Type 2):

   • For each observation deck \(p\) in the range \([a, b]\), compute \(L_p + R_p\).
   • If \(L_p = \frac{best\_ln}{best\_ld}\) and \(R_p = \frac{best\_rn}{best\_rd}\), their sum is: $\(L_p + R_p = \frac{best\_ln \times best\_rd + best\_rn \times best\_ld}{best\_ld \times best\_rd}\)$
   • Compare this fraction with the current minimum (tentative best) by cross-multiplying, and update the \(p\) that gives the minimum.
   • If values are equal, prioritize the smaller index \(p\) as specified in the problem statement.

Complexity

• Time Complexity: \(O(Q \times N^2)\)
  • For each query, computing \(L_p, R_p\) for all observation decks takes \(O(N^2)\), and finding the minimum within the range takes \(O(N)\).
• Space Complexity: \(O(N)\)
  • Memory needed to store mountain heights and computed \(L_p, R_p\) values.

Implementation Notes

• Comparison by Cross-Multiplication: When computing \(L_p\) and \(R_p\), as well as when comparing their sums, always use comparisons in the form a * d < c * b.

• Setting Initial Values: When searching for the minimum of \(L_p + R_p\), either use the value of the first observation deck \(p=a\) as the initial value, or set a sufficiently large fraction (as a substitute for infinity) as the initial value.

• Handling 1-indexed Arrays: The problem uses observation decks \(1 \sim N\). Be careful about index offsets, such as by making the array size \(N+1\).

  Source Code

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

This editorial was generated by gemini-3-flash-thinking.