分数: 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