问题陈述
有一个序列 N 之间的整数 0 和 10,包括: A = (A_1, A_2, \dots, A_N).
流程 Q 下面按给出的顺序描述查询。
每个查询有三个整数 C, L,和 R。根据其值进行如下操作 C.
- If C = 1:排序 A_L, A_{L+1}, \dots, A_R 按升序排列。
- If C = 2:排序 A_L, A_{L+1}, \dots, A_R 按降序排列。
- If C = 3:打印 \displaystyle \sum_{i=L}^R A_i.
约束
- 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
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出,其中 \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
输出
打印 T 行,其中 T 是查询的数量 C = 3.
的 i第行 (1 \leq i \leq T) 应包含以下问题的答案 i第一个查询 C = 3.
示例输入 1
5 5 1 0 8 2 10 3 2 4 1 1 4 3 2 4 2 3 5 3 2 4
示例输出 1
10 11 19
最初, A = (1, 0, 8, 2, 10).
对于第一个查询,答案是 0 + 8 + 2 = 10.
第二次查询后, A is (0, 1, 2, 8, 10).
对于第三个查询,答案是 1 + 2 + 8 = 11.
第四次查询后, A is (0, 1, 10, 8, 2).
对于第五个查询,答案是 1 + 10 + 8 = 19.