← 返回题目列表

AtCoder · abc389_c

E. 蛇队列

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

分数: 300 点

问题陈述

有一条蛇在排队。最初,队列是空的。

你被给予 Q 查询,应按照给出的顺序进行处理。查询分为三种类型:

  • 类型 1:以表格形式给出 1 l。一条蛇的长度 l 被添加到队列末尾。如果添加前队列为空,则新添加的snake的头位置为 0;否则,就是队列中最后一条蛇的头部坐标与最后一条蛇的长度之和。
  • 类型 2:以表格形式给出 2。队列前面的蛇离开队列。保证此时队列不为空。让 m 为离开的蛇的长度,则队列中剩余的每条蛇的头部坐标减少 m.
  • 类型 3:以表格形式给出 3 k。输出蛇的头部坐标 k- 从队列前面算起的第一个。保证至少有 k 此时蛇在队列中。

约束

  • 1 \leq Q \leq 3 \times 10^{5}
  • 对于类型的查询 1, 1 \leq l \leq 10^{9}
  • 对于类型的查询 2,保证队列不为空。
  • 对于类型的查询 3,让 n 是队列中蛇的数量,那么 1 \leq k \leq n.
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

在这里, \text{query}_i 是 i-第一个查询采用以下形式之一:

1 l
2
3 k

输出

让 q 是该类型的查询数量 3。打印 q 行。的 i- 第行应包含以下问题的答案 i第类型 3 查询。


示例输入 1

7
1 5
1 7
3 2
1 3
1 4
2
3 3

示例输出 1

5
10
  • 第一个查询:一条长度的蛇 5 已添加到队列中。由于队列是空的,所以这条蛇的头部坐标是 0.
  • 第二个查询:一条长度的蛇 7 已添加到队列中。添加之前,最后一条蛇有头部坐标 0 和长度 5,所以新添加的蛇头坐标为 5.
  • 第三个查询:输出从前面数第二条蛇的头部坐标。目前,蛇的头部坐标依次为 0, 5,所以输出 5.
  • 第四个查询:一条长度为多少的蛇 3 已添加到队列中。添加之前,最后一条蛇有头部坐标 5 和长度 7,所以新的蛇头坐标为 12.
  • 第 5 个查询:一条长度的蛇 4 已添加到队列中。添加之前,最后一条蛇有头部坐标 12 和长度 3,所以新的蛇头坐标为 15.
  • 第 6 个查询:前面的蛇离开队列。剩下的蛇的长度是 5,因此剩余的每条蛇的头部坐标减少 5。剩下的蛇头坐标变成 0, 7, 10.
  • 第7条查询:输出从前面数第3条蛇的头部坐标。目前,蛇的头部坐标依次为 0, 7, 10,所以输出 10.

示例输入 2

3
1 1
2
1 3

示例输出 2


可能没有类型的查询 3.


示例输入 3

10
1 15
1 10
1 5
2
1 5
1 10
1 15
2
3 4
3 2

示例输出 3

20
5