题目描述

线段树是非常神奇的数据结构，能快速实现区间操作。RMQ（Range Maximum Query）是线段树的基础应用。 本题是一个练习RMQ的题目，单刀直入，给你两种操作：

• 1 $i\ x$ 将数组的第 $i$ 个元素修改为 $x$。
• 2 $l\ r$ 查询 $[l,r]$ 区间的最大值。

输入格式

第一行两个整数 $n,m$，代表数组元素的个数和操作次数。

第二行是 $n$ 个整数 $x_i$，代表数组元素的初始值。

接下来 $m$ 行，每行有三个整数，有 1 $i\ x$ 或者 2 $l\ r$ 两种形式。

输出格式

对于每个1操作，输出全局最大值，对于每个2操作，输出查询区间的最大值。

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

4
10
10
4
3

数据规模

对于所有数据，保证 $1≤n,m≤200000, 1≤l≤r≤n，1≤i≤n，1≤x,x_i≤10^9$。

前四组数据较小，方便验证正确性。本题时限不需要用快读快写。