Overview

For each observation deck \(p\), we express “how much the mountains on the left and right block the view” as the maximum slope (height ÷ distance), and the problem asks us to answer interval queries for the observation deck that maximizes \(V_p=\dfrac{1}{1+L_p+R_p}\). Since heights can be updated, we need to precisely compare \(V_p\) values each time to find the best index.

Analysis

Key Observation 1: \(L_p, R_p\) are determined by the “maximum ratio (fraction)”

For the left direction: $\(L_p=\max_{1\le l<p}\frac{H_l}{p-l}\)\( The right direction is analogous. In other words, we only need to know the maximum "line-of-sight slope" created by each mountain to the left (or right) as seen from \)p$.

For example, when \(p=5\), for left positions \(l=2,4\): - \(l=2\): \(\dfrac{H_2}{3}\) - \(l=4\): \(\dfrac{H_4}{1}\)

We compare these, and the larger one becomes \(L_5\).

Key Observation 2: Comparing \(V_p\) values with floating point is dangerous

\(V_p\) is a rational number, and the problem statement says to “compare with exact values.” Comparing with floating point (float) can cause the ordering to flip due to precision errors, leading to WA.

Therefore, we store fractions as integer numerator and denominator pairs, and compare using $\(\frac{a}{b}>\frac{c}{d}\iff ad>cb\)$ i.e., cross multiplication (overflow might be a concern, but Python’s integers have arbitrary precision, so it’s safe).

Why a naive approach is fast enough

Since \(N,Q\le 200\) are small, for each type 2 query we can: - For each \(p\in[a,b]\), compute \(L_p\) in \(O(N)\) and \(R_p\) in \(O(N)\) - Find the maximum \(V_p\) among them

This brute-force approach is fast enough (at most around \(200 \times 200 \times 200\)).

Algorithm

1. Computing \(L_p, R_p\) as fractions for a given \(p\)

• Brute-force search over all \(l\) that maximize \(L_p\), taking the maximum of the fraction \(\dfrac{H_l}{p-l}\)
  Comparison is done via cross multiplication:
  • Current maximum is \(\dfrac{Lnum}{Lden}\)
  • New candidate is \(\dfrac{num}{den}=\dfrac{H_l}{p-l}\)
  • Update if num * Lden > Lnum * den
• \(R_p\) is computed similarly (brute-force search over right positions \(r\))

2. Constructing \(V_p=\dfrac{1}{1+L_p+R_p}\) as a fraction

Let \(L=\dfrac{Lnum}{Lden},\; R=\dfrac{Rnum}{Rden}\), then $\(1+L+R=1+\frac{Lnum}{Lden}+\frac{Rnum}{Rden} =\frac{Lden\cdot Rden + Lnum\cdot Rden + Rnum\cdot Lden}{Lden\cdot Rden}\)\( Therefore \)\(V_p=\frac{1}{1+L+R} =\frac{Lden\cdot Rden}{Lden\cdot Rden + Lnum\cdot Rden + Rnum\cdot Lden}\)$ In code: - Vnum = Lden * Rden - Vden = Vnum + Lnum * Rden + Rnum * Lden

and we return \((Vnum, Vden)\).

3. Type 2 Query (maximum \(V_p\) in an interval)

• Iterate over \(p=a..b\), computing \(V_p\) for each
• Compare the maximum fraction using cross multiplication
  To compare \(\dfrac{x}{y}\) and \(\dfrac{u}{v}\), compare x*v and u*y
• In case of a tie, choose the smaller index (since we scan from left to right, we handle this precisely by including p < best_p in the update condition when values are equal)

4. Type 1 Query (update)

Simply set H[x] = h. The next type 2 query will recompute using the updated array.

Complexity

• Time complexity:
  For each type 2 query, assuming the interval length is at most \(N\), computing \(L,R\) for each \(p\) takes \(O(N)\), so one query is \(O(N^2)\).
  Overall, at most \(O(QN^2)\) (around \(200\cdot 200^2=8\times 10^6\)).
• Space complexity: \(O(N)\) (only the height array and a constant number of variables)

Implementation Notes

• Always store fractions as integer pairs (numerator, denominator): Do not use float.

• Compare using cross multiplication: a/b > c/d becomes a*d > c*b.

• When \(p=1\), there is nothing to the left, so \(L_p=0\); when \(p=N\), there is nothing to the right, so \(R_p=0\). In the code, we initialize to (0,1) to handle this naturally.

• When there is a tie for the maximum, choose the smaller index. Don’t forget to handle the equal case in comparisons.

  Source Code

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

---

This editorial was generated by gpt-5.2-high.