AT_past202303_o 区間ソートクエリ

$ 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 $ を出力する。

入力は以下の形式で標準入力から与えられる。ここで $ \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 $ であるクエリに対する答えを出力せよ。

### Sample Explanation 1 はじめ、 $ 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 $ です。 ### 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 $ - 入力される値はすべて整数