U187874 动态峰值问题

`Mr.Wang` : 谁来解决这个困难的问题? `YJY` : 这个题太水了,我的小弟都能解决. 于是这个拯救不了世界的重担就落在了你的身上.

有 $n$ 个人排成一列, 每个人都有一个能力值 $A_i$,`Mr.Wang` 将会对这些人进行一些操作: 操作一,选取一个指定位置的人,将其替换为另一个人. 操作二,询问 $[l,r]$ 内 $A_i$ 的最大值. 因为 `Mr.Wang` 没有很多人手,所以操作一最多有 $50$ 次.

第一行两个整数 $n,q$ ,代表有 $n$ 个人 和 $q$ 次操作. 第二行 $n$ 个整数,第 $i$ 个为 $A_i$ 的值. 接下来的 $q$ 行: 输入一个整数 $op$; 若 $op=1$ , 输入两个整数 $a,b$ ,代表将 $a$ 处的人换为一个能力值为 $b$ 的人. 否则,输入两个整数 $l,r$ ,你需要输出 $[l,r]$ 内能力值最高的人.

对于每个操作二,输出一行一个整数,代表区间内能力值最高的人.如果区间内无人，输出 $0$.

**本题输入输出量极大，请采用较快的读入方式。** |子任务 |数据限制 |分值 | | :-----------: | :-----------: | :-----------: | |subtask 1 | $n\le 15,q\le20$ | 5 | | subtask 2 | $n\le 300,q\le 3\times 10^4$ | 15 | | subtask 3 | $n\le 10^3 ,q\le 6\times 10^5$ | 35 | | subtask 4| $n\le 1.5\times 10^3,q\le 2\times 10^7$ | 45 | 保证 $0\le A_i \le 6 \times 10^4$.