B - Choosing an Observation Deck Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 333 点

問題文

高橋君は山岳地帯をハイキングしており、一直線上に等間隔に並んだ N 個の展望台から景色を眺めようとしています。展望台には左から順に 1, 2, \ldots, N の番号がついており、展望台 i と展望台 j の間の距離は |i - j| です。

各展望台 i の地点には高さ H_i の山がそびえています。高橋君がある展望台に立って左右を見渡すとき、他の展望台の地点にある山が視界を遮るため、見える空の広さが変わります。

具体的に、高橋君が展望台 p に立ったとき、見渡せる「空の広さ」を次のように定義します。高橋君の目線の高さは 0 とします。なお、展望台 p 自身の地点にある山は高橋君の視界を遮らないものとします。

  • 左方向の遮り度：展望台 p から左方向を見たとき、展望台 l（l < p）の山が視界を遮る度合いを、距離に対する高さの比 \frac{H_l}{p - l} で表します。左方向の遮り度を

L_p = \max_{1 \le l < p} \frac{H_l}{p - l}

と定義します。ただし p = 1 のときは左に展望台が存在しないため、L_p = 0 とします。

  • 右方向の遮り度：同様に、右方向の遮り度を

R_p = \max_{p < r \le N} \frac{H_r}{r - p}

と定義します。ただし p = N のときは右に展望台が存在しないため、R_p = 0 とします。

  • 空の広さ：展望台 p における空の広さは

V_p = \frac{1}{1 + L_p + R_p}

です。

ところが、山岳地帯では工事や自然現象によって山の高さが時々変化します。

Q 個のイベントが順番に発生します。各イベントは以下の 2 種類のいずれかです。

  • タイプ 1：展望台 x の地点にある山の高さが h に変わる（すなわち H_x の値が h に更新される）。
  • タイプ 2：展望台 a から展望台 b まで（a \le b）の範囲にある展望台の中で、その時点での「空の広さ」V_p が最大となる展望台の番号を求める。最大となる展望台が複数ある場合は、最も番号の小さいものを答える。

なお、V_p の比較は厳密な値（有理数）に基づいて行われます。

各タイプ 2 のイベントについて、答えを求めてください。

制約

  • 1 \leq N \leq 200
  • 1 \leq Q \leq 200
  • 1 \leq H_i \leq 10^9（1 \leq i \leq N）
  • タイプ 1 のイベントにおいて、1 \leq x \leq N かつ 1 \leq h \leq 10^9
  • タイプ 2 のイベントにおいて、1 \leq a \leq b \leq N
  • タイプ 2 のイベントは 1 つ以上存在する
  • 入力はすべて整数で与えられる

入力

N Q
H_1 H_2 \ldots H_N
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

各クエリは以下のいずれかの形式で与えられます。

1 x h

2 a b
  • 1 行目には、展望台の数 N とイベントの数 Q がスペース区切りで与えられる。
  • 2 行目には、各展望台の地点にある山の初期の高さ H_1, H_2, \ldots, H_N がスペース区切りで与えられる。
  • 3 行目から Q 行にわたって、各イベントの情報が 1 行ずつ与えられる。
  • タイプ 1 のイベントは 1 x h の形式で、展望台番号 x と新しい山の高さ h が与えられる。
  • タイプ 2 のイベントは 2 a b の形式で、範囲の左端 a と右端 b が与えられる。

出力

タイプ 2 のイベントごとに、「空の広さ」V_p が最大となる展望台の番号を 1 行に 1 つずつ出力せよ。

入力例 1

5 3
3 1 4 1 5
2 1 5
2 3 4
2 5 5

出力例 1

1
3
5

入力例 2

3 4
10 1 10
2 1 3
1 2 100
2 1 3
2 2 2

出力例 2

1
2
2

入力例 3

10 8
5 3 8 2 7 1 9 4 6 3
2 1 10
2 3 7
1 5 100
2 1 10
1 7 1
2 5 9
2 1 1
2 10 10

出力例 3

1
3
5
5
1
10

入力例 4

20 15
12 5 18 3 25 7 14 9 30 2 11 6 22 8 17 4 28 1 19 10
2 1 20
2 5 15
1 9 1
2 1 20
1 1 1000000000
2 1 5
2 18 20
1 17 1
2 10 20
2 1 20
1 5 1
1 15 500
2 1 20
2 7 13
2 19 20

出力例 4

1
9
1
1
20
20
1
1
13
20

入力例 5

1 1
1000000000
2 1 1

出力例 5

1

Score : 333 pts

Problem Statement

Takahashi is hiking in a mountainous area and wants to enjoy the scenery from N observation decks arranged in a straight line at equal intervals. The observation decks are numbered 1, 2, \ldots, N from left to right, and the distance between observation deck i and observation deck j is |i - j|.

At each observation deck i, there stands a mountain of height H_i. When Takahashi stands at an observation deck and looks around to the left and right, mountains at other observation deck locations obstruct his view, changing the amount of visible sky.

Specifically, when Takahashi stands at observation deck p, the "sky openness" is defined as follows. Takahashi's eye level is 0. Note that the mountain at observation deck p itself does not obstruct Takahashi's view.

  • Left obstruction degree: When looking left from observation deck p, the degree to which the mountain at observation deck l (l < p) obstructs the view is represented by the ratio of height to distance \frac{H_l}{p - l}. The left obstruction degree is defined as

L_p = \max_{1 \le l < p} \frac{H_l}{p - l}

However, when p = 1, there are no observation decks to the left, so L_p = 0.

  • Right obstruction degree: Similarly, the right obstruction degree is defined as

R_p = \max_{p < r \le N} \frac{H_r}{r - p}

However, when p = N, there are no observation decks to the right, so R_p = 0.

  • Sky openness: The sky openness at observation deck p is

V_p = \frac{1}{1 + L_p + R_p}

However, in the mountainous area, mountain heights occasionally change due to construction or natural phenomena.

Q events occur in order. Each event is one of the following two types:

  • Type 1: The height of the mountain at observation deck x changes to h (i.e., the value of H_x is updated to h).
  • Type 2: Among the observation decks in the range from observation deck a to observation deck b (a \le b), find the observation deck number with the maximum "sky openness" V_p at that point in time. If there are multiple observation decks with the maximum value, output the one with the smallest number.

Note that comparisons of V_p are performed based on exact values (rational numbers).

For each Type 2 event, find the answer.

Constraints

  • 1 \leq N \leq 200
  • 1 \leq Q \leq 200
  • 1 \leq H_i \leq 10^9 (1 \leq i \leq N)
  • For Type 1 events, 1 \leq x \leq N and 1 \leq h \leq 10^9
  • For Type 2 events, 1 \leq a \leq b \leq N
  • There is at least one Type 2 event
  • All input values are integers

Input

N Q
H_1 H_2 \ldots H_N
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

Each query is given in one of the following formats:

1 x h

2 a b
  • The first line contains the number of observation decks N and the number of events Q, separated by a space.
  • The second line contains the initial heights of the mountains at each observation deck H_1, H_2, \ldots, H_N, separated by spaces.
  • The following Q lines each contain information about one event.
  • A Type 1 event is given in the format 1 x h, where the observation deck number x and the new mountain height h are given.
  • A Type 2 event is given in the format 2 a b, where the left endpoint a and right endpoint b of the range are given.

Output

For each Type 2 event, output the observation deck number with the maximum "sky openness" V_p, one per line.

Sample Input 1

5 3
3 1 4 1 5
2 1 5
2 3 4
2 5 5

Sample Output 1

1
3
5

Sample Input 2

3 4
10 1 10
2 1 3
1 2 100
2 1 3
2 2 2

Sample Output 2

1
2
2

Sample Input 3

10 8
5 3 8 2 7 1 9 4 6 3
2 1 10
2 3 7
1 5 100
2 1 10
1 7 1
2 5 9
2 1 1
2 10 10

Sample Output 3

1
3
5
5
1
10

Sample Input 4

20 15
12 5 18 3 25 7 14 9 30 2 11 6 22 8 17 4 28 1 19 10
2 1 20
2 5 15
1 9 1
2 1 20
1 1 1000000000
2 1 5
2 18 20
1 17 1
2 10 20
2 1 20
1 5 1
1 15 500
2 1 20
2 7 13
2 19 20

Sample Output 4

1
9
1
1
20
20
1
1
13
20

Sample Input 5

1 1
1000000000
2 1 1

Sample Output 5

1