Overview

In this problem, we need to answer queries about which observation deck has the widest “sky width” when viewing scenery from observation decks lined up in a straight line. We also need to handle events where mountain heights are changed.

Analysis

First, the “sky width” \(V_p\) at each observation deck \(p\) can be calculated as follows:

• Maximum slope in the left direction: \(L_p = \max_{l < p} \frac{H_l}{p - l}\)
• Maximum slope in the right direction: \(R_p = \max_{r > p} \frac{H_r}{r - p}\)
• Sky width: \(V_p = \frac{1}{1 + L_p + R_p}\)

To perform slope comparisons and additions accurately, we can use Python’s fractions.Fraction for error-free computation.

In a naive approach, for each type 2 query, we compute \(L_p\) and \(R_p\) by brute force for each observation deck in the range, requiring \(O(N^2)\) computation in the worst case. Since the constraints are \(N, Q \leq 200\), the maximum number of operations is approximately \(200 \times 200 \times 200 = 8,000,000\), which is fast enough.

Therefore, a simple brute-force implementation is sufficiently fast for this problem.

Algorithm

1. For each type 2 query, for each observation deck \(p\) in the interval \([a, b]\):
   • Compute \(L_p\) by looking from \(l = 1\) to \(p-1\) and finding the maximum slope
   • Compute \(R_p\) by looking from \(r = p+1\) to \(N\) and finding the maximum slope
   • Calculate \(V_p = \frac{1}{1 + L_p + R_p}\)
2. Among those with the maximum \(V_p\), select the smallest \(p\)
3. For type 1 queries, simply update the value in the array \(H\)

All computations are performed exactly using Fraction, and comparisons are also exact.

Complexity

• Time complexity: \(O(Q \cdot N^2)\)
  For each type 2 query, computing the left and right slopes for each point in the interval takes up to \(O(N)\), so the overall complexity is \(O(Q \cdot N^2)\)
• Space complexity: \(O(N)\)
  Only the array \(H\) storing heights and a few variables are used

Implementation Notes

• Using floating-point numbers can cause precision errors, so use fractions.Fraction for exact computation

• Be careful that indices are 1-based (handle the array as 1-indexed)

• For type 2 queries, when multiple observation decks have the same maximum value, note that the one with the smallest index must be selected

  Source Code

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

This editorial was generated by qwen3-coder-480b.