AT_abc389_c [ABC389C] Snake Queue

题目描述

存在一个蛇的队列。初始时队列为空。

给定 $Q$ 个查询，请按顺序处理。查询有以下三种类型：

• 类型 1：以 1 l 的形式给出。将长度为 $l$ 的蛇添加到队列末尾。此时，若原队列为空，则添加的蛇的头部坐标为 $0$；否则，新蛇的头部坐标为队列最后一条蛇的头部坐标加上其长度。
• 类型 2：以 2 的形式给出。队列最前端的蛇离开队列。此时保证队列不为空。设离开的蛇长度为 $m$，队列中剩余所有蛇的头部坐标将减少 $m$。
• 类型 3：以 3 k 的形式给出。输出队列中从前往后数第 $k$ 条蛇的头部坐标。此时保证队列中至少有 $k$ 条蛇。

输入格式

输入通过标准输入给出，格式如下：

$Q$

$\text{query}_1$

$\text{query}_2$

$\vdots$

$\text{query}_Q$

其中，$\text{query}_i$ 表示第 $i$ 个查询，为以下形式之一：

$1$ $l$

$2$

$3$ $k$

输出格式

设类型 3 的查询共有 $q$ 个，输出 $q$ 行。第 $i$ 行输出第 $i$ 个类型 3 查询的答案。

输入输出样例 #1

输入 #1

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

输出 #1

5
10

输入输出样例 #2

输入 #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

说明/提示

约束条件

• $1 \leq Q \leq 3 \times 10^{5}$
• 类型 1 的查询中，$1 \leq l \leq 10^{9}$
• 类型 2 的查询保证队列不为空
• 类型 3 的查询中，设队列中有 $n$ 条蛇，则 $1 \leq k \leq n$
• 输入均为整数

样例解释 1

• 第 1 个查询：添加长度为 $5$ 的蛇。队列为空，因此其头部坐标为 $0$。
• 第 2 个查询：添加长度为 $7$ 的蛇。原最后一条蛇的头部坐标为 $0$ 且长度为 $5$，因此新蛇的头部坐标为 $5$。
• 第 3 个查询：输出第 2 条蛇的头部坐标。队列中蛇的头部坐标依次为 $0, 5$，因此输出 5。
• 第 4 个查询：添加长度为 $3$ 的蛇。原最后一条蛇的头部坐标为 $5$ 且长度为 $7$，因此新蛇的头部坐标为 $12$。
• 第 5 个查询：添加长度为 $4$ 的蛇。原最后一条蛇的头部坐标为 $12$ 且长度为 $3$，因此新蛇的头部坐标为 $15$。
• 第 6 个查询：移除队列最前端的蛇（长度为 $5$）。剩余蛇的头部坐标减少 $5$，此时坐标为 $0, 7, 10$。
• 第 7 个查询：输出第 3 条蛇的头部坐标。队列中蛇的头部坐标依次为 $0, 7, 10$，因此输出 10。

样例解释 2

可能存在没有类型 3 查询的情况。

翻译由 DeepSeek R1 完成