C - Large Queue Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

空の整数列 A=() があります。クエリが Q 個与えられるので、与えられた順に処理してください。クエリは以下の 2 種類です。

  • タイプ 1 : 1 c x の形式で与えられる。A の末尾に x を c 個追加する。
  • タイプ 2 : 2 k の形式で与えられる。A の先頭 k 要素を削除し、削除した k 個の整数の総和を出力する。このとき、k はその時点での A の長さ以下であることが保証される。

制約

  • 1 \leq Q \leq 2 \times 10^{5}
  • タイプ 1 のクエリにおいて、 1 \leq c \leq 10^{9}
  • タイプ 1 のクエリにおいて、 1 \leq x \leq 10^{9}
  • タイプ 2 のクエリにおいて、その時点での A の長さを n として、 1 \leq k \leq \min(10^{9},n)
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

ただし、 \text{query}_i は i 個目のクエリを表し、以下のいずれかの形式である。

1 c x

2 k

出力

タイプ 2 のクエリの個数を q として、q 行出力せよ。i 行目には、i 個目のタイプ 2 のクエリに対する答えを出力せよ。

入力例 1

5
1 2 3
1 4 5
2 3
1 6 2
2 5

出力例 1

11
19
  • 1 個目のクエリ: A の末尾に 3 を 2 個追加する。このとき、A=(3,3) となる。
  • 2 個目のクエリ: A の末尾に 5 を 4 個追加する。このとき、A=(3,3,5,5,5,5) となる。
  • 3 個目のクエリ: A の先頭 3 要素を削除する。このとき、削除した 3 個の整数の総和は 3+3+5=11 となるため 11 と出力する。削除後、A=(5,5,5) となる。
  • 4 個目のクエリ: A の末尾に 2 を 6 個追加する。このとき、A=(5,5,5,2,2,2,2,2,2) となる。
  • 5 個目のクエリ: A の先頭 5 要素を削除する。このとき、削除した 5 個の整数の総和は 5+5+5+2+2=19 となるため 19 と出力する。削除後、A=(2,2,2,2) となる。

入力例 2

10
1 75 22
1 81 72
1 2 97
1 84 82
1 2 32
1 39 57
2 45
1 40 16
2 32
2 42

出力例 2

990
804
3024

入力例 3

10
1 160449218 954291757
2 17217760
1 353195922 501899080
1 350034067 910748511
1 824284691 470338674
2 180999835
1 131381221 677959980
1 346948152 208032501
1 893229302 506147731
2 298309896

出力例 3

16430766442004320
155640513381884866
149721462357295680

Score : 300 points

Problem Statement

There is an empty integer sequence A=(). You are given Q queries, and you need to process them in the given order. There are two types of queries:

  • Type 1: Given in the format 1 c x. Add c copies of x to the end of A.
  • Type 2: Given in the format 2 k. Remove the first k elements from A and output the sum of the removed k integers. It is guaranteed that k is at most the length of A at that time.

Constraints

  • 1 \leq Q \leq 2 \times 10^{5}
  • In type 1 queries, 1 \leq c \leq 10^{9}.
  • In type 1 queries, 1 \leq x \leq 10^{9}.
  • In type 2 queries, letting n be the length of A at that time, 1 \leq k \leq \min(10^{9},n).
  • All input values are integers.

Input

The input is given from standard input in the following format:

Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

where \text{query}_i represents the i-th query and is in one of the following formats:

1 c x

2 k

Output

Let q be the number of type 2 queries. Output q lines. The i-th line should contain the answer to the i-th type 2 query.

Sample Input 1

5
1 2 3
1 4 5
2 3
1 6 2
2 5

Sample Output 1

11
19
  • 1st query: Add 2 copies of 3 to the end of A. Then, A=(3,3).
  • 2nd query: Add 4 copies of 5 to the end of A. Then, A=(3,3,5,5,5,5).
  • 3rd query: Remove the first 3 elements from A. Then, the sum of the removed 3 integers is 3+3+5=11, so output 11. After removal, A=(5,5,5).
  • 4th query: Add 6 copies of 2 to the end of A. Then, A=(5,5,5,2,2,2,2,2,2).
  • 5th query: Remove the first 5 elements from A. Then, the sum of the removed 5 integers is 5+5+5+2+2=19, so output 19. After removal, A=(2,2,2,2).

Sample Input 2

10
1 75 22
1 81 72
1 2 97
1 84 82
1 2 32
1 39 57
2 45
1 40 16
2 32
2 42

Sample Output 2

990
804
3024

Sample Input 3

10
1 160449218 954291757
2 17217760
1 353195922 501899080
1 350034067 910748511
1 824284691 470338674
2 180999835
1 131381221 677959980
1 346948152 208032501
1 893229302 506147731
2 298309896

Sample Output 3

16430766442004320
155640513381884866
149721462357295680