O - 区間ソートクエリ 解説 /

実行時間制限: 6 sec / メモリ制限: 1024 MiB

問題文

0 以上 10 以下の整数からなる長さ N の数列 A = (A_1, A_2, \dots, A_N) があります。
以下に説明するクエリを与えられる順に Q 個処理してください。

各クエリでは 3 つの整数 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 を出力する。

制約

  • 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

出力

C = 3 であるクエリの個数を T として、T 行出力せよ。
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) です。
1 番目のクエリの答えは 0 + 8 + 2 = 10 です。
2 番目のクエリを処理した後の A は (0, 1, 2, 8, 10) です。
3 番目のクエリの答えは 1 + 2 + 8 = 11 です。
4 番目のクエリを処理した後の A は (0, 1, 10, 8, 2) です。　
5 番目のクエリの答えは 1 + 10 + 8 = 19 です。

Problem Statement

There is a sequence of N integers between 0 and 10, inclusive: A = (A_1, A_2, \dots, A_N).
Process Q queries described below in the order they are given.

Each query has three integers C, L, and R. Do the following according to the value of C.

  • If C = 1: sort A_L, A_{L+1}, \dots, A_R in ascending order.
  • If C = 2: sort A_L, A_{L+1}, \dots, A_R in descending order.
  • If C = 3: print \displaystyle \sum_{i=L}^R A_i.

Constraints

  • 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
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format, where \text{Query}_i denotes the i-th query:

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

Each query is in the following format:

C L R

Output

Print T lines, where T is the number of queries with C = 3.
The i-th line (1 \leq i \leq T) should contain the answer to the i-th query with C = 3.

Sample Input 1

5 5
1 0 8 2 10
3 2 4
1 1 4
3 2 4
2 3 5
3 2 4

Sample Output 1

10
11
19

Initially, A = (1, 0, 8, 2, 10).
For the first query, the answer is 0 + 8 + 2 = 10.
After the second query, A is (0, 1, 2, 8, 10).
For the third query, the answer is 1 + 2 + 8 = 11.
After the fourth query, A is (0, 1, 10, 8, 2).
For the fifth query, the answer is 1 + 10 + 8 = 19.