分数: 400 点
问题陈述
我们有一个水平圆柱体。 给定 Q 查询,按给定顺序处理它们。
每个查询属于以下两种类型之一。
1 x c:插入 c 球,带有编号 每张纸上都写有 x ,位于圆柱体的右端。2 c:取出 c 圆柱体中最左边的球,并打印已取出的球上写的数字的总和。
我们假设球在圆柱体中永远不会改变它们的顺序。
约束
- 1 \leq Q \leq 2\times 10^5
- 0 \leq x \leq 10^9
- 1 \leq c \leq 10^9
- 每当查询类型
给出
2 c,有 气缸中有 c 或更多球。 - 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
Q
{\rm query}_1
\vdots
{\rm query}_Q
的 树的 i第一个查询 {\rm query}_i 采用以下两种格式之一。
1 x c
2 c
输出
打印对 type 查询的响应 2 c 按照给定的顺序,中间有换行符。
示例输入 1
4 1 2 3 2 2 1 3 4 2 3
示例输出 1
4 8
- 对于 1-st 查询,插入 3 球,带有编号
每张纸上都写有 2 ,位于圆柱体的右端。
圆柱体现在有带有数字的球 上面从左到右写着 (2,2,2) 。 - 对于 2-nd查询,取出 2 最左边的球包含在圆柱体中。
取出的球上写的数字是 2,2,总和 4,应打印。 圆柱体现在有一个带有数字的球 上面从左到右写着 (2) 。 - 对于 3-rd 查询、插入 4 球,带有编号
每张纸上都写有 3 ,位于圆柱体的右端。
圆柱体现在有带有数字的球 上面从左到右写着 (2,3,3,3,3) 。 - 对于 4第查询,取出 3 最左边的球包含在圆柱体中。
取出的球上写的数字是 2,3,3,总和 8,应打印。 圆柱体现在有带有数字的球 (3,3) 。
示例输入 2
2 1 1000000000 1000000000 2 1000000000
示例输出 2
1000000000000000000
示例输入 3
5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
示例输出 3
可能没有您应该打印的内容。