这是问题的困难版本。它与简单方法的区别仅在于 $$$n$$$ 和 $$$t$$$ 的约束。
有一副 $$$n$$$ 牌,每张牌都有其威力。卡有两种类型:
- 英雄卡牌,该卡牌的力量始终等于$$$0$$$;
- 一张奖励卡,此类卡的威力始终为正。
您可以对牌组执行以下操作:
- 从牌堆顶取出一张牌;
- 如果这张卡是奖励卡,你可以将其放在你的奖励卡组顶部或丢弃;
- 如果这张卡是英雄卡,那么你的奖励卡组顶牌的力量将被添加到他的力量中(如果它不为空),之后该英雄被添加到你的军队中,并且使用的奖励被丢弃。
你的任务是利用这些行动来聚集一支拥有最大可能总力量的军队。
输入
输入数据的第一行包含单个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试中的测试用例数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 这副牌中的牌数。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$s_1, s_2, \dots, s_n$$$ ($$$0 \le s_i \le 10^9$$$) - 卡牌能力按自上而下的顺序排列。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
输出$$$t$$$个数字,每个数字都是相应测试用例的答案——军队可以达到的最大可能总战力。
示例
输入 #1
5 5 3 3 3 0 0 6 0 3 3 0 0 3 7 1 2 3 0 4 5 0 7 1 2 5 0 4 3 0 5 3 1 0 0 4
输出 #1
6 6 8 9 4
注意
在第一个示例中,您可以获得奖金 $$$1$$$ 和 $$$2$$$。两张英雄卡都将获得 $$$3$$$ 力量。如果您拿走所有奖金,其中一项将保持未使用状态。
在第二个示例中,牌组顶部的英雄卡牌无法启动,其余的可以通过 $$$2$$$ 和 $$$3$$$ 奖励进行启动并获得 $$$6$$$ 总能量。
在第四个示例中,您可以获取奖金$$$1$$$、$$$2$$$、$$$3$$$、$$$5$$$并跳过奖金$$$6$$$,然后英雄$$$4$$$将获得$$$3$$$奖金$$$5$$$的增强,而英雄$$$7$$$将获得奖金$$$5$$$的增强$$$4$$$。 $$$4+5=9$$$。