CF1055B Alice and Hairdresser

Alice 的头发正在飞速生长。也许是因为维生素摄入过量，也许是某种黑魔法…… 为了防止头发继续疯长，Alice 决定去理发店。她希望剪完头发后，每根头发的长度都不超过 $l$ 厘米，其中 $l$ 是她最喜欢的数字。假设 Alice 的头是一直线，共有 $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$），表示每根头发的初始长度。 接下来的 $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$），表示第 $p_i$ 根头发增长了 $d_i$ 厘米。

对于每个类型为 $0$ 的询问，输出当前理发需要的时间（秒数）。

考虑第一个样例： - 初始时头发长度为 $1, 2, 3, 4$，只有第 $4$ 根头发长度大于 $l=3$，理发师可以在 $1$ 秒内剪完。 - 然后第 $2$ 根头发增长，长度变为 $1, 5, 3, 4$。 - 现在理发需要 $2$ 秒：第 $4$ 根头发和第 $2$ 根头发各需要一次剪刀。 - 然后第 $1$ 根头发增长，长度变为 $4, 5, 3, 4$。 - 现在理发仍需 $2$ 秒：第 $4$ 根头发和第 $1$、$2$ 根头发组成的区间各需要一次剪刀。 - 然后第 $3$ 根头发增长，长度变为 $4, 5, 4, 4$。 - 现在理发只需 $1$ 秒：可以一刀剪掉第 $1$ 到第 $4$ 根头发。 由 ChatGPT 4.1 翻译