← 返回题目列表

Codeforces · 1266/E

E. 宇宙飞船纸牌

中文机器翻译题面 查看原题

Bob 正在玩太空飞船纸牌游戏。这个游戏的目标是建造一艘宇宙飞船。为此,他首先需要积累足够的建设资源。有 $$$n$$$ 类型的资源,编号为 $$$1$$$ 到 $$$n$$$。 Bob 至少需要第 $$$i$$$ 资源中的 $$$a_i$$$ 块来建造宇宙飞船。数字 $$$a_i$$$ 称为资源 $$$i$$$ 的目标。

每个资源需要 $$$1$$$ 轮次来生产,并且每一轮只能生产一个资源。然而,有一些里程碑可以加快生产速度。每个里程碑都是三重 $$$(s_j, t_j, u_j)$$$,这意味着一旦 Bob 拥有 $$$t_j$$$ 单位的资源 $$$s_j$$$,他就可以免费获得一个单位的资源 $$$u_j$$$,而无需花费一回合。获得此免费资源可能会让 Bob 获得另一个里程碑的奖励。这样一来,他就能在一个回合内获得大量的资源。

游戏的构建方式是,永远不会有两个具有相同$$$s_j$$$和$$$t_j$$$的里程碑,也就是说,达到$$$t_j$$$单位资源$$$s_j$$$的奖励至多是一个额外资源。

任何资源的 $$$0$$$ 都不会获得奖金,无论是达到目标 $$$a_i$$$ 还是超过目标 - 正式而言,对于每个里程碑 $$$0 < t_j < a_{s_j}$$$。

达到一定数量资源的奖励可以是资源本身,即$$$s_j = u_j$$$。

最初没有里程碑。您将处理 $$$q$$$ 更新,每个更新都会添加、删除或修改一个里程碑。每次更新后,输出完成游戏所需的最小回合数,即为[1, n]$$$中的每个$$$i积累至少$$$a_i$$$第$$$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$$$),其中第 $$$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$$$ 表示第 $$$i$$$ 更新后的答案。

示例

输入 #1

2
2 3
5
2 1 1
2 2 1
1 1 1
2 1 2
2 2 0

输出 #1

4
3
3
2
3

注意

第一次更新后,最优策略如下。首先生产$$$2$$$一次,这会提供免费资源$$$1$$$。然后,产生 $$$2$$$ 两次,$$$1$$$ 一次,总共四轮。

第二次更新后,最佳策略是生产 3 次 $$$2$$$ — 前两次也授予单个资源单位 $$$1$$$。

第三次更新后,游戏获胜方式如下。

- 首先产生 $$$2$$$ 一次。这给出了 $$$1$$$ 的免费单位。这会带来资源 $$$1$$$ 的额外奖励。第一轮之后,资源数量为 $$$[2, 1]$$$。
- 接下来,再次生产资源$$$2$$$,这给出了另一个单位$$$1$$$。
- 此后,再生产一单位$$$2$$$。

最终资源数为$$$[3, 3]$$$,需要三轮才能达到这种情况。请注意,我们拥有的资源 $$$1$$$ 比其目标多,这是没有用的。