← 返回题目列表

Codeforces · 1055/B

B. 爱丽丝和理发师

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

爱丽丝的头发长得突飞猛进。可能是维生素过多的原因,也可能是某种黑魔法……

为了防止这种情况发生,爱丽丝决定去理发店。她希望理发后头发长度最多为 $$$l$$$ 厘米,其中 $$$l$$$ 是她最喜欢的数字。假设爱丽丝的头部是一条直线,$$$n$$$ 发际线在这条直线上生长。我们将它们从 $$$1$$$ 到 $$$n$$$ 编号。只要剪刀一挥,美发师就可以将任何部分上的所有发际线缩短到长度$$$l$$$,假设该部分上的所有发际线的长度严格大于$$$l$$$。理发师希望尽快完成工作,因此他会尽可能少地挥动剪刀,因为每次挥动剪刀都需要一秒钟。

Alice还没有决定什么时候去理发店,所以她让你根据她去理发店的时间来计算理发需要多长时间。特别是,您需要处理两种类型的查询:

- $$$0$$$ — Alice 询问如果她现在去理发店理发需要多长时间。
- $$$1$$$ $$$p$$$ $$$d$$$ — 第 $$$p$$$ 发际线增长了 $$$d$$$ 厘米。

请注意,在请求 $$$0$$$ 中,Alice 对现在理发的假设场景感兴趣,因此发际线的长度不会改变。

输入

第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$l$$$ ($$$1 \le n, m \le 100\,000$$$, $$$1 \le l \le 10^9$$$)——发际线的数量、请求的数量和 Alice 最喜欢的数量。

第二行包含 $$$n$$$ 整数 $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$) — Alice 所有发际线的初始长度。

以下 $$$m$$$ 行中的每一行均包含语句中描述的格式的请求。

请求描述以整数 $$$t_i$$$ 开头。如果 $$$t_i = 0$$$,那么您需要找到理发所需的时间。否则,$$$t_i = 1$$$,此时一根发际线开始生长。该行的其余部分包含两个以上的整数:$$$p_i$$$ 和 $$$d_i$$$ ($$$1 \le p_i \le n$$$, $$$1 \le d_i \le 10^9$$$) — 发际线的数量及其增长的长度。

输出

对于 $$$0$$$ 类型的每个查询,打印理发所需的时间。

示例

输入 #1

4 7 3
1 2 3 4
0
1 2 3
0
1 1 3
0
1 3 1
0

输出 #1

1
2
2
1

注意

考虑第一个示例:

- 最初发际线的长度等于$$$1, 2, 3, 4$$$,只有第$$$4$$$发际线更长$$$l=3$$$,理发师可以在$$$1$$$秒内剪掉它。
- 然后爱丽丝的第二条发际线开始生长,发际线的长度现在等于 $$$1, 5, 3, 4$$$
- 现在理发需要两秒:需要两次摆动:第$$$4$$$发际线和第$$$2$$$发际线。
- 然后爱丽丝的第一条发际线开始生长,发际线的长度现在等于 $$$4, 5, 3, 4$$$
- 理发仍然需要两秒钟:理发师一次挥动即可剪掉第 $$$4$$$ 发际线,再挥动一次即可剪掉从 $$$1$$$-st 到 $$$2$$$-nd 发际线的部分。
- 然后爱丽丝的第三条发际线开始生长,发际线的长度现在等于 $$$4, 5, 4, 4$$$
- 现在理发只需要一秒钟:只要一挥动,就可以剪掉从第 $$$1$$$ 发际线到第 $$$4$$$ 发际线的部分。