P9742 「KDOI-06-J」贡献系统

洛谷贡献系统上线了！ 现在有 $n$ 个人即将参加一场洛谷月赛，每个人的等级分**互不相同**。第 $i$ 个人的等级分是 $r_i$，贡献值是 $c_i$。 假设第 $i$ 个人的等级分在这 $n$ 个人中的排名是 $a_i$（排名按等级分从大到小排序），且在月赛中的排名是 $b_i$，没有两个人的排名相同。也就是说，$a$ 和 $b$ 都是 $1$ 到 $n$ 的排列。比赛结束后，每个人都会执行以下操作： + 若 $a_i=b_i$，则第 $i$ 个人的等级分不会发生任何变化，因此第 $i$ 个人不会进行任何操作； + 若 $a_i>b_i$，则第 $i$ 个人的等级分会上升，因此第 $i$ 个人会给出题人点赞，导致出题人的贡献值上升 $c_i$（$c_i$ 可能是负数，此时会导致出题人的贡献值下降）； + 若 $a_i

无

无

**【样例解释 #1】** 对于第一组测试数据，设五个人按输入顺序分别为 A，B，C，D，E，则当月赛中的排名顺序为 ABECD 时贡献值最大，为 $0+0-(-50)-(-22)+208=280$。可以证明，这是唯一能使贡献值达到最大的排名顺序。 对于第二组测试数据，设八个人按输入顺序分别为 A，B，C，D，E，F，G，H，则当月赛中的排名顺序为 ABCDEGFH 时可以使贡献值达到最大值 $1$，注意此时有多种可能的使贡献值最大的排名顺序。 **【样例 #2】** 见选手目录下的 `contrib/contrib2.in` 与 `contrib/contrib2.ans`。 **【样例 #3】** 见选手目录下的 `contrib/contrib3.in` 与 `contrib/contrib3.ans`。 *** **【数据范围】** 对于所有数据保证：$1\le T\le 5$，$1\le n\le 2\times 10^5$，$0\le r_i\le 10^9$，$-10^9\le c_i\le 10^9$，且对于任意 $1\le ir_{i+1}$。 | 测试点编号 | $n\le $ | 特殊限制 | | :---------: | :------------: | :------: | | $1\sim3$ | $8$ | 无 | | $4$ | $100$ | ABC | | $5$ | $100$ | C | | $6\sim 7$ | $100$ | 无 | | $8\sim 9$ | $5\times 10^3$ | AB | | $10\sim 11$ | $5\times 10^3$ | C | | $12\sim 14$ | $5\times 10^3$ | 无 | | $15$ | $2\times10^5$ | AB | | $16\sim 18$ | $2\times10^5$ | B | | $19\sim 21$ | $2\times10^5$ | C | | $22\sim 25$ | $2\times 10^5$ | 无 | + 特殊性质 A：对于任意 $1\le i