P15901 [TOPC 2025] Reactor

在一个高科技工业设施中，一系列核反应堆呈线性排列。每个反应堆都在严格的压力规范下运行，以确保安全和效率。为了防止关键性故障，每个反应堆都有一个特定的最大压力限值。当反应堆的内部压力达到或超过该限值时，就会启动受控泄压（排气）。由于运行调整的动态性和持续监测的需求，该系统需要复杂的管理。 你的任务是设计并实现一个系统，来管理一排 $n$ 个反应堆的压力。每个反应堆从 $1$ 到 $n$ 编号，初始最大压力限值为 $p_i$。所有反应堆的初始压力均为 $0$。该系统必须支持两种操作： 1. **增压操作**：对于给定区间 $[l, r]$ 内的反应堆，将其压力增加 $k$ 个单位。如果该区间内任意反应堆的压力达到或超过其最大限值，则该反应堆将泄压，其压力重置为 $0$。并且泄压反应堆的最大压力限值将被更新为 $\max(\lfloor \frac{p_{old}}{2} \rfloor, 1)$，其中 $p_{old}$ 是该反应堆在本次增压操作前的最大压力限值。 2. **泄压次数查询**：对于给定区间 $[l, r]$ 内的反应堆，你需要报告自系统开始运行以来，该指定区间内所有反应堆发生泄压的总次数。

第一行包含两个整数 $n$ 和 $q$，分别表示反应堆的数量和操作的数量。 第二行包含 $n$ 个整数，其中第 $i$ 个整数 $p_i$ 表示第 $i$ 个反应堆的初始最大压力限值。 接下来的 $q$ 行描述操作。每行以一个整数 $op$ 开头。 - 如果 $op = 1$，则后面跟三个整数 $l$、$r$ 和 $k$，表示对区间 $[l, r]$ 内的反应堆进行压力增加 $k$ 个单位的增压操作。 - 如果 $op = 2$，则后面跟两个整数 $l$ 和 $r$，表示对区间 $[l, r]$ 内的反应堆进行泄压次数查询。

对于每个 $op = 2$ 的查询，在新的一行输出一个整数，表示自系统开始运行以来，指定区间内所有反应堆发生泄压的总次数。

- $1 \le n \le 2 \times 10^5$ - $1 \le q \le 2 \times 10^5$ - $1 \le p_i \le 4 \times 10^5$ - $1 \le l \le r \le n$ - $1 \le k \le 4 \times 10^5$ - 保证至少有一个泄压次数查询。 翻译由 DeepSeek V3.2 完成