← 返回题目列表

AtCoder · awc0083_b

B. 选择观景台

中文机器翻译题面 查看原题

分数: 333 分

问题陈述

高桥正在山区徒步旅行,想要欣赏来自 N 观景台等间隔排列成直线。观景台有编号 1, 2, \ldots, N 从左到右,与观景台之间的距离 i 和观景台 j is |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}

However, when p = 1,左边没有观景台,所以 L_p = 0.

  • Right obstruction degree:同样,右阻塞度定义为

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

However, when p = N,右侧没有观景台,所以 R_p = 0.

  • 天空开放: 观景台的天空开阔 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 事件按顺序发生。每个事件都是以下两种类型之一:

  • 类型 1: 观景台的山高 x 更改为 h (i.e., the value of H_x is updated to h).
  • 类型 2: Among the observation decks in the range from observation deck a 前往观景台 b (a \le b),找到“天空开放度”最大的观景台编号 V_p at that point in time.如果存在多个具有最大值的观景台,则输出编号最小的观景台。

Note that comparisons of 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)
  • For Type 1 events, 1 \leq x \leq N 和 1 \leq h \leq 10^9
  • For Type 2 events, 1 \leq a \leq b \leq N
  • 至少有一个 2 类事件
  • 所有输入值均为整数

输入

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
  • 第一行包含观景台的数量 N 和事件数量 Q,用空格分隔。
  • 第二行包含每个观景台的山脉初始高度 H_1, H_2, \ldots, H_N,用空格分隔。
  • The following Q 行每一行都包含有关一个事件的信息。
  • 类型 1 事件以以下格式给出 1 x h,其中观景台编号 x 和新的山高 给出了 h 。
  • 类型 2 事件以以下格式给出 2 a b,其中左端点 a 和右端点 给出了范围的 b 。

输出

对于每个类型 2 事件,输出具有最大“天空开放度”的观景台编号 V_p,每行一个。


样本输入 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