T584467 「2025 YAC Round 5」小五的宠物训练

小五想要训练她的宠物阿空。 小五有 $n$ 个小怪 $a_1, a_2, \ldots, a_n$。第 $i$ 个小怪的战斗力为 $a_i$。阿空的初始耐力值为 $M$。 定义如下流程为一场训练： - 从第 $1$ 个小怪开始，每个小怪依次对阿空进行攻击。第 $i$ 个小怪对阿空进行攻击，阿空的耐力值 $M$ 会减去 $a_i$，然后这一轮的第 $i$ 个小怪的战斗力 $a_i$ **翻倍**。在这一轮的第 $n$ 个小怪攻击完后，重新从第 $1$ 个小怪开始重复执行此流程，进行下一轮。 - 当 $M \le 0$ 时，即阿空耐力耗尽时，本场训练立刻结束。 每场训练结束后，阿空的耐力值会恢复为初始的 $M$，每个小怪的战斗力变为这场训练之前的 $a_i$。 现在一共进行 $q$ 场训练，每场训练之前小五会对区间 $[l, r]$ 内的小怪提升 $d$ 点战斗力，然后再正式开始这场训练。对于每场训练，小五想要知道阿空能够承受 **多少次** 小怪的攻击（不包括恰好使阿空耐力耗尽的一次）。 **注意：每场训练之前对小怪的战斗力的提升会对之后所有训练产生影响。**

第一行输入三个整数 $n,q,M$（$1 \le n \le 2 \times 10^5$，$1 \le q \le 10^6$，$1 \le M \le 10^{18}$），分别表示小怪个数、训练场数、阿空的初始耐力值。 第二行输入 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^{6}$），表示每个小怪的初始战斗力。 接下来 $q$ 行，第 $i$ 行输入三个整数 $l,r,d$（$1 \le l \le r \le n$，$1 \le d \le 2^{15}$），表示第 $i$ 场训练前小怪战斗力提升的参数。

输出共 $q$ 行。 第 $i$ 行输出一个数 $s$，表示第 $i$ 场训练阿空能够承受 **多少次** 小怪的攻击（不包括恰好使阿空耐力耗尽的一次）。

一共三场训练。三场训练前的强化分别是： - 对 $[1,5]$ 的小怪增加 $1$ 点战斗力。 - 对 $[3,4]$ 的小怪增加 $2$ 点战斗力。 - 对 $[1,2]$ 的小怪增加 $2$ 点战斗力。 第 $1$ 场训练，经过提升后小怪的初始战斗力分别为 $4, 3, 2, 5, 3$。 阿空 第一轮分别依次受到这些小怪的攻击各一次，此时剩余耐力值 $18$。小怪战斗力变为 $8, 6, 4, 10, 6$。 接着 阿空 受到第一只小怪的攻击，剩余耐力值为 $10$。 受到第二只小怪攻击，剩余耐力值 $4$。 受到第三只小怪攻击，剩余耐力值 $0$。 因为不包括恰好使阿空耐力耗尽的一次攻击，所以本场训练共承受了 $5+2=7$ 次攻击。 第 $2$ 场训练，经过提升后小怪的初始战斗力分别为 $4, 3, 4, 7, 3$。 第 $3$ 场训练，经过提升后小怪的初始战斗力分别为 $6, 5, 4, 7, 3$。 可以得出第 $2, 3$ 场训练承受攻击次数分别为 $6, 5$。