← 返回题目列表

AtCoder · past202303_o

O. 区间排序查询

中文机器翻译题面 查看原题

问题陈述

有一个序列 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.