1437. 区间最值查询

给一个数组 aa,接下来有若干操作:

  • 操作 11,给定 id,valid,val,将 aida_{id} 设置为 valval
  • 操作 22,给定 L,RL,R,回答 maxi=LRai\max_{i=L}^{R}a_i 的值。

输入

第一行一个整数 n,q (1n,q105)n,q \ (1 \leq n,q \leq 10^5),数组长度和操作数量。

接下来一行 nn 个整数 a1,a2,...,an (1ai109)a_1,a_2,...,a_n \ (1 \leq a_i \leq 10^9)

接下来 qq 行,每行三个整数,第一个数 opr (1opr2)opr \ (1 \leq opr \leq 2) 表示操作类型。

  • 如果 opr=1opr=1,接下来读入两个整数 id,val (1idn,1val109)id,val \ (1 \leq id \leq n, 1 \leq val \leq 10^9)
  • 如果 opr=2opr=2,接下来读入两个整数 L,R (1LRn)L,R \ (1 \leq L \leq R \leq n)

本题所有测试点均为随机数据。

输出

对于每个询问,输出一行一个整数,表示答案。

样例

标准输入 复制文本
5 3
1 3 5 4 2
1 2 4
2 1 5
2 1 2
标准输出 复制文本
5
4
登录以提交代码。
单点时限 2 秒
内存限制 1024 MB
提交 97
通过 33