← 返回题目列表

AtCoder · abc413_c

F. 大队列

中文机器翻译题面 查看原题

分数: 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