为了便于表述，下文中用"数"替代怪物的血量。
我们换一种不同于 easy version 中的计算答案的方法。
我们先还是按照 easy version 中的贪心操作来消除，当一个数能通过这种贪心策略被操作 $2$ 消除为 $0$，那我们就称这个数是多余的。
举个例子，例如 $\{1,1,2\}$ 中的第二个 $1$ 就是多余的，因为我们可以通过使用操作 $2$ 消除第一个 $1$ 来使第二个 $1$ 变为 $0$，但第一个 $1$ 就并不是多余的。
很显然，当一个数为 $i$，小于等于 $i$ 的数（不包含它本身）的数量大于等于 $i$ 时，$i$ 就是一个多余的数。因为多余的数并不会对答案有影响，所以我们可以直接删去这些数。
设 $b$ 为当前前缀删去多余的数后的数列，$p$ 为 $b$ 的长度，那么答案就是 $\sum_{i = 1}^{p} (b_i - i)$，化简一下就是 $\sum_{i = 1}^{p} b_i - \frac{p(p+1)}{2}$。
设 $cnt_i$ 为当前 $i$ 出现的次数，可以用权值线段树去维护 $\min x - \sum_{i=1}^{x} cnt_i$，当它为负数时就代表当前出现了多余的数，一直搜到当前最小的多余的数并把它删除即可。
我们枚举每个前缀，然后依次加入当前前缀新增的数，并删除掉多余的数，时间复杂度为 $O(n\log n)$。
标签：前缀,题解,sum,hard,CF1784C,version,多余,当前 From： https://www.cnblogs.com/kowenxrz/p/17114017.html