AT_past202303_o.区間ソートクエリ

有一个长度为 $N$ 的整数序列 $A = (A_1, A_2, \dots, A_N)$，其中每个数的取值范围为 $0$ 到 $10$（包括 $0$ 和 $10$）。
你需要按顺序处理 $Q$ 个操作。

每个操作包含三个整数 $C$、$L$ 和 $R$，根据 $C$ 的值，执行以下操作：

• 如果 $C = 1$：将 $A_L, A_{L+1}, \dots, A_R$ 升序排序。
• 如果 $C = 2$：将 $A_L, A_{L+1}, \dots, A_R$ 降序排序。
• 如果 $C = 3$：输出 $\displaystyle \sum_{i=L}^R A_i$。

输入由标准输入给出，格式如下，其中 $\text{Query}_i$ 表示第 $i$ 个操作：

$N\ Q\ A_1\ A_2\ \dots\ A_N\ \text{Query}_1\ \text{Query}_2\ \vdots\ \text{Query}_Q$

每个操作格式为：

$C\ L\ R$

对于每个 $C=3$ 的操作，输出一行。
第 $i$ 行（$1 \leq i \leq T$）输出第 $i$ 个 $C=3$ 操作的答案。

样例解释 1

初始时，$A = (1, 0, 8, 2, 10)$。
第一个操作，输出 $0+8+2=10$。
第二个操作后，$A$ 变为 $(0,1,2,8,10)$。
第三个操作，输出 $1+2+8=11$。
第四个操作后，$A$ 变为 $(0,1,10,8,2)$。
第五个操作，输出 $1+10+8=19$。

数据范围

• $1 \leq N \leq 5 \times 10^5$
• $1 \leq Q \leq 2 \times 10^4$
• $0 \leq A_i \leq 10$
• $1 \leq C \leq 3$
• $1 \leq L \leq R \leq N$
• 输入的所有值均为整数。

由 ChatGPT 5 翻译