問題一覧 > 通常問題

No.1441 MErGe

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 59
作問者 : ir_1st_vilir_1st_vil / テスター : 沙耶花沙耶花
4 ProblemId : 5398 / 出題時の順位表
問題文最終更新日: 2021-03-26 20:52:10

注意

この問題の実行時間制限は $1$ 秒です。

問題文

長さ $N$ の数列 $A$ が与えられます。これに対する $Q$ 個のクエリを処理してください。与えられるクエリには以下の二種類があります。

  • タイプ $1$ : $A_l,A_{l+1},\dots,A_r$ を数列から削除し、削除する前の数列における $\displaystyle \sum_{i=l}^{r}A_i$ をその位置に挿入する(このとき $A$ の添え字は改めて昇順に振り分けられる)。
  • タイプ $2$ : その時点での $\displaystyle \sum_{i=l}^{r}A_i$ を出力する。

入力

$N\ Q$
$A_1\ A_2\ \dots\ A_N$
$T_1\ l_1\ r_1$
$T_2\ l_2\ r_2$
$\vdots$
$T_Q\ l_Q\ r_Q$
  • 入力は全て整数
  • $1 \le N \le 2 \times 10^5$
  • $1 \le Q \le 2 \times 10^5$
  • $|A_i| \le 10^9$
  • $1 \le T_i \le 2$
  • $i$ 個目のクエリ直前の $A$ の長さを $N_i$ として $1 \le l_i \le r_i \le N_i$
  • 各テストケースにタイプ $2$ のクエリは $1$ つ以上存在する
$i$ 個目のクエリではタイプ $T_i$ のクエリを $l=l_i,r=r_i$ として処理してください。

出力

タイプ $2$ の各クエリについて各時点での $\displaystyle \sum_{i=l}^{r}A_i$ を改行区切りで出力し、最後に改行してください。

サンプル

サンプル1
入力
10 5
6 5 5 3 5 1 3 5 3 3
2 1 9
1 2 7
2 2 3
1 1 2
2 3 3
出力
36
27
3

$A$ はクエリ $2$ で $(6,22,5,3,3)$ に、クエリ $4$ で $(28,5,3,3)$ にそれぞれ変化します。

サンプル2
入力
16 9
-4 -2 -4 -1 -3 -3 7 7 5 -1 -1 6 5 10 -2 3
2 8 13
2 9 9
1 16 16
1 3 8
2 7 7
1 7 8
2 6 10
1 8 10
1 2 6
出力
21
5
6
21

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。