A4587 | $可变数组$

来源官方 / 2024

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

给定一个长度为 $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{数据范围}$ - $1 \le N, Q\le 10^6$ - $1 \le A_i \le 10^9$ - $1 \le T_i \le 4$ - $1 \le P_i \le N(T_i = 1)$ - $1 \le X_i \le 10^9(T_i = 1, 4)$ - $1 \le L_i \le R_i \le N(T_i = 2, 3, 4)$

对于每个输入文件，格式如下： > $\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

C++ 编辑器

输入

输出