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