4326. I Hate It

【题目背景】

——以爱与正义之名，魔法少女❤——闪亮登场！！！

【题目描述】

给定一个长度为 $n$ 的正整数序列 $A_1, A_2, \dots, A_n$，初始时已知所有元素的值。接下来需要处理 $m$ 个操作，每个操作是以下两种类型之一：

查询操作 `Q l r`：查询区间 $[l, r]$ 内的最大值，即 $\max_{i=l}^r A_i$。

更新操作 `U i x`：将 $A_i$ 更新为 $\max(A_i, x)$。

请处理所有操作，并对每个查询操作输出相应的结果。

【输入格式】

第一行包含两个正整数 $n$ 和 $m$（$1 \le n, m \le 2 \times 10^5$），分别表示序列的长度和操作的个数。

第二行包含 $n$ 个正整数 $A_1, A_2, \dots, A_n$（$1 \le A_i \le 10^9$），表示序列的初始值。

接下来 $m$ 行，每行描述一个操作。每行首先是一个字符 $c$，表示操作类型：

若 $c$ 为 `Q`，则随后有两个正整数 $l$ 和 $r$（$1 \le l \le r \le n$），表示一个查询操作。

若 $c$ 为 `U`，则随后有两个正整数 $i$ 和 $x$（$1 \le i \le n$, $1 \le x \le 10^9$），表示一个更新操作。

【输出格式】

对于每个查询操作，输出一行一个整数，表示对应区间内的最大值。

【样例输入】

5 3
1 2 3 4 5
Q 1 5
U 1 6
Q 1 5

【样例输出】

5
6

【数据规模与约定】

对于 $100\%$ 的数据，$1 \le n, m \le 2 \times 10^5$，$1 \le A_i, x \le 10^9$。