分数: 300 点
问题陈述
有一个空整数序列 A=()。你被给予 Q 查询,您需要按照给定的顺序处理它们。有两种类型的查询:
- 类型 1:以格式给出
1 c x。添加 c 副本 x 到年底 A. - 类型 2:以格式给出
2 k。删除第一个 k 元素来自 A 并输出移除的总和 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 查询,让 n 的长度 A 当时, 1 \leq k \leq \min(10^{9},n).
- 所有输入值均为整数。
输入
输入由标准输入给出,格式如下:
Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q
其中 \text{query}_i 代表 i-th 查询,采用以下格式之一:
1 c x
2 k
输出
让 q 是类型的数量 2 查询。输出 q 行。 的 i- 第行应包含以下问题的答案 i第类型 2 查询。
示例输入 1
5 1 2 3 1 4 5 2 3 1 6 2 2 5
示例输出 1
11 19
- 1st 查询:添加 2 副本 3 到年底 A。然后, A=(3,3).
- 2nd查询:添加 4 副本 5 到年底 A。然后, A=(3,3,5,5,5,5).
- 3rd 查询:删除第一个 3 元素来自 A。然后,删除的总和 3 整数是 3+3+5=11,所以输出 11。移除后, A=(5,5,5).
- 4第查询:添加 6 副本 2 到年底 A。然后, A=(5,5,5,2,2,2,2,2,2).
- 5第一个查询:删除第一个 5 元素来自 A。然后,删除的总和 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