← 返回题目列表

AtCoder · abc247_d

G. 气缸

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

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


可能没有您应该打印的内容。