#10696. D - Cylinder 圆柱体 比赛编号247

D - Cylinder 圆柱体 比赛编号247

问题描述

我们有一个水平的圆柱体。给定 Q 个查询,按照给定的顺序处理它们。每个查询是以下两种类型之一:

  1. 1 x c:向圆柱体的右端插入 c 个球,每个球上写有数字 x
  2. 2 c:取出圆柱体中最左边的 c 个球,并打印出这些球上数字的和。

我们假设球在圆柱体中的顺序永远不会改变。

输入

输入格式如下:

Q
query1
query2
...
queryQ

每个查询 queryi 是以下两种格式之一:

  • 1 x c:表示插入 c 个数字为 x 的球。
  • 2 c:表示取出 c 个最左边的球,并计算它们的和。

输出

对于每个 2 c 类型的查询,输出这些球的数字之和,并在每个输出结果之间换行。

限制

  • 1 ≤ Q ≤ 2 × 10^5
  • 0 ≤ x ≤ 10^9
  • 1 ≤ c ≤ 10^9
  • 每当有类型为 2 c 的查询时,圆柱体中至少有 c 个球。
  • 输入的所有值都是整数。

样例输入 1

4
1 2 3
2 2
1 3 4
2 3

样例输出 1

4
8

解释​:

  • 第1个查询:插入3个数字为2的球,圆柱体现在有(2, 2, 2)这三个球。
  • 第2个查询:取出圆柱体中最左边的2个球,取出的球是(2, 2),它们的和为4,输出4。
  • 第3个查询:插入4个数字为3的球,圆柱体现在有(2, 3, 3, 3, 3)这五个球。
  • 第4个查询:取出圆柱体中最左边的3个球,取出的球是(2, 3, 3),它们的和为8,输出8。

样例输入 2

2
1 1000000000 1000000000
2 1000000000

样例输出 2

1000000000000000000

解释​:

  • 第1个查询:插入1000000000个数字为1000000000的球,圆柱体现在有1000000000个数字为1000000000的球。
  • 第2个查询:取出1000000000个最左边的球,取出的球是(1000000000,1000000000,...),它们的和是 1000000000 * 1000000000,输出 1000000000000000000

样例输入 3

5
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1

样例输出 3

(没有输出)

解释​:

  • 所有的查询都是插入球的操作,且没有任何 2 c 类型的查询,因此没有输出。

解题思路

这个问题可以使用队列(Queue)来模拟。对于每个查询:

  1. ​**类型 1 x c**​:将 c 个数字为 x 的球插入到队列的末尾。
  2. ​**类型 2 c**​:从队列的前面取出 c 个球,并计算它们的和。

因为输入的 Q 查询数量最大为 2 * 10^5,所以我们需要确保每个操作的时间复杂度尽可能低。队列(deque)适合用来执行这种插入和删除操作,因为其时间复杂度是常数级别的。