Overview

This problem involves calculating the “sky broadness” from each observation deck as the heights of mountains arranged in a straight line change, and finding the observation deck with the broadest visible sky within a specified range.

Analysis

The core of the problem is to calculate the “obstruction degree” \(L_p\) and \(R_p\) in the left and right directions for each observation deck \(p\), and then compute the sky broadness \(V_p = \frac{1}{1 + L_p + R_p}\). The obstruction degree represents how much other observation deck mountains block the view as the ratio of height to distance \(\frac{H_i}{|p-i|}\), taking the maximum of these values.

Since the constraints are small with \(N, Q \leq 200\), it is feasible to naively compute \(L_p\) and \(R_p\) for all observation decks for each query. There is no need to consider more efficient algorithms (e.g., convex hull techniques), and the problem can be solved with a simple nested loop.

Algorithm

1. Maintain an array \(H\) of mountain heights.
2. Process each query in order:
   • Type 1 (Update): Update \(H[x]\) to the new value \(h\).
   • Type 2 (Query): For each observation deck \(p\) in the range \([a, b]\), compute the following:
     • \(L_p\): Compute the maximum of \(\frac{H_l}{p-l}\) over all observation decks \(l\) to the left of \(p\) (0 if \(p=1\)).
     • \(R_p\): Compute the maximum of \(\frac{H_r}{r-p}\) over all observation decks \(r\) to the right of \(p\) (0 if \(p=N\)).
     • Compute \(V_p = \frac{1}{1 + L_p + R_p}\).
3. Find the \(p\) that maximizes \(V_p\) (in case of ties, choose the smallest index).

Complexity

• Time complexity: \(O(Q \cdot N^2)\)
  • Each Type 2 query requires \(O(N^2)\) computation (checking all observation decks to the left and right for each \(p\)).
  • Since the maximum values of \(N, Q\) are 200, the maximum number of operations is \(200 \cdot 200^2 = 8,000,000\), which is sufficiently fast.
• Space complexity: \(O(N)\)
  • The size of the array storing mountain heights is \(N\).

Implementation Notes

• For floating-point comparisons, it is safe to use a tolerance such as abs(Vp - best_v) < 1e-12 to account for errors (however, since this problem only involves integer divisions, exact rational number comparison is possible, but floating-point numbers are used for implementation simplicity).

• Since array indices are handled as 1-indexed, the array size is set to \(n+1\), using indices from 1 to n.

• Since mountain heights are updated with each query, always use the latest \(H\) for calculations.

  Source Code

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

This editorial was generated by deepseekv3.