CF1266E Spaceship Solitaire

Bob 在玩一款叫 *Spaceship Solitaire* 的游戏。游戏的核心是建造一艘宇宙飞船。为了建造，他首先需要积累足够的资源。有 $n$ 种资源，从 $1$ 到 $n$ 标号，Bob 需要 $a_i$ 个第 $i$ 种资源来建造飞船。我们称 $a_i$ 为资源 $i$ 的目标。 一回合能且只能生产一个资源。但是，有一些“成就”可以加快生产速度。每个成就可以用一个三元组表示 $(s_j, t_j, u_j)$，意思是当 Bob 拥有的第 $s_j$ 种资源个数达到 $t_j$ 时，他可以获得一个免费的第 $u_j$ 种资源。获得此免费资源有可能使 Bob 要求获得另一个成就的奖励。 不会有两个成就含有相同的 $s_j$ 和 $t_j$，也就是说，达到资源 $t_j$ 个资源 $s_j$ 的奖励最多是一个额外的资源。 对于每个成就，有 $0 < t_j < a_{s_j}$。 达到一定资源量的奖励可以是这个资源本身，也就是 $s_j = u_j$。 最开始时没有成就的。你需要处理 $q$ 次更新，可能是添加，删除或改变成就。在每次更新后，输出完成游戏（也就是对于每个资源 $i \in [1, n]$，收集至少 $a_i$ 个）所需的最小回合数。

第一行有一个整数 $n(1 \leq n \leq 2 \cdot 10^5)$，表示资源的种类数。 第二行共有$n$个以空格分隔的整数 $a_1, a_2, \dots, a_n (1 \leq a_i \leq 10^9)$，$a_i$ 表示需要收集第 $i$ 种资源的个数。 第三行有一个整数 $q(1 \leq q \leq 10^5)$，表示更新的个数。 接下来有 $q$ 行，第 $j$ 行有三个以空格分隔的整数 $s_j,t_j,u_j(1 \leq s_j \leq n,1 \leq t_j < a_{s_j},0 \leq u_j \leq n)$ 对于每个三元组，执行以下操作： - 首先，如果已经存在一个当积累了 $t_j$ 个 $s_j$ 种资源时给予奖励的成就，则将其删除。 - 如果 $u_j = 0$，则不执行操作。 - 如果 $u_j \neq 0$，则添加如下成就：“当积累了 $t_j$ 个 $s_j$ 种资源时，赠送一个免费的 $u_j$ 种资源”。 - 输出完成游戏所需的最少回合数。

输出共 $q$ 行，每行一个整数，表示第 $i$ 次修改之后的答案。

第一次更新后，最优策略如下：首先生产一次 $2$，这将提供一个免费资源 $1$。然后，产生两次 $2$ 和一次 $1$，总共四个回合。 在第二次更新之后，最优策略是生产三次 $2$ ——前两次也授予单个单位的资源 $1$。 在第三次更新之后，游戏的获胜情况如下。 - 首先生成 $2$ 一次。这给出了一个自由单位 $1$。这提供了额外的资源 $1$。在第一轮之后，资源的数量为 $[2, 1]$。 - 接下来，再次生产资源 $2$，这将获得另一个单位 $1$。 - 之后，再生产一个单位的 $2$。 最终的资源计数为 $[3, 3]$，需要三个回合才能达到这个情况。注意，我们拥有的资源 $1$ 比它的目标多，这是没有用的。