可变数组_信奥算法普及+/提高

给定一个长度为 $N$ 的数组 $A_1, A_2, \cdots, A_N$ 。

你需要执行 $Q$ 个操作，第 $i$ 个操作的类型为 $T_i$ ：

$T_i = 1$ ：给定两个整数 $P_i$ 和 $X_i$ ，将 $A_{P_i}$ 的值替换为 $X_i$ 。
$T_i = 2$ ：给定两个整数 $L_i$ 和 $R_i$ ，交换 $A_{L_i}$ 和 $A_{R_i}$ 的值。
$T_i = 3$ ：给定两个整数 $L_i$ 和 $R_i$ ，查询 $A_{L_i}, A_{L_i + 1}, \cdots, A_{R_i}$ 中的最大值。
$T_i = 4$ ：给定三个整数 $X_i$ ， $L_i$ 和 $R_i$ ，查询数组中 $[L_i, R_i]$ 中第一个大于等于 $X_i$ 的元素的下标，即满足 $L_i \le j \le R_i, A_j \ge X_i$ 的最小的 $j$ ；如果 $L_i$ 到 $R_i$ 中的没有任何 $j$ 满足条件，则输出 $-1$ 。

$\large{数据范围}$

对于每个输入文件，格式如下：

$\tt{N\ Q}$
$\tt{A_1\ A_2\ \cdots\ A_N}$
$\tt{Query_1}$
$\tt{Query_2}$
$\tt{\vdots}$
$\tt{Query_Q}$

对于每个 $\tt{Query_i}$ 格式如下：

若 $T_i = 1$ ：

$\tt{T_i\ P_i\ X_i}$

若 $T_i = 2, 3$ ：

$\tt{T_i\ L_i\ R_i}$

若 $T_i = 4$ ：

$\tt{T_i\ X_i\ L_i\ R_i}$

对于每个 $T_i = 3, 4$ 的查询，在单独的一行输出答案。

输入#1

6 7
7 1 3 5 2 5
3 1 6
4 3 2 5
1 6 9
2 3 5
4 3 2 5
3 1 6
4 10 3 6

输出#1

输入#2

17 11
18 10 12 7 1 12 9 3 6 13 11 7 1 13 11 5 20
3 10 14
2 1 16
4 17 1 12
1 9 12
1 13 3
1 17 14
4 6 4 13
1 3 11
3 13 16
4 19 11 15
4 12 8 15

输出#2

$\bf{样例\ 1：}$

$(A_1, A_2, A_3, A_4, A_5, A_6) = (7, 1, 3, 5, 2, 5)$ 的最大值为 $7$ ，故输出 $7$ 。
$(A_2, A_3, A_4, A_5) = (1, 3, 5, 2)$ 中第一个大于等于 $3$ 的元素为 $A_3 = 3$ ，故输出 $3$ 。
将 $A_6$ 的值修改为 $9$ ，此时数组 $A = (7, 1, 3, 5, 2, 9)$ 。
交换 $A_3$ 和 $A_5$ 的值，此时数组 $A = (7, 1, 2, 5, 3, 9)$ 。
$(A_2, A_3, A_4, A_5) = (1, 2, 5, 3)$ 中第一个大于等于 $3$ 的元素为 $A_4 = 5$ ，故输出 $4$ 。
$(A_1, A_2, A_3, A_4, A_5, A_6) = (7, 1, 2, 5, 3, 9)$ 中的最大值为 $9$ ，故输出 $9$ 。
$(A_3, A_4, A_5, A_6) = (2, 5, 3, 9)$ 中不存在大于等于 $10$ 的数字，故输出 $-1$ 。

A33359.可变数组