AT_abc389_c [ABC389C] Snake Queue

[problemUrl]: https://atcoder.jp/contests/abc389/tasks/abc389_c 存在一个蛇的队列。初始时队列为空。 给定 $ 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 \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 完成