QOJ 7787 Max Rating 题解

最近几天讲临项交换，突然想到以前洛谷网校模拟赛做到了这么一个有意思的题目，然后找了一下午，好几次都略过了这道题目但是就是没看出来就是我要找的那道题。开原题机发现是这道题目。

▶

INFO 题面 T529359

放的是网校的题面，题号也是网校的题号，防止自己忘记。和 QOJ 7787 是一道题目。

小 M 参加了 次 1v1 比赛，其中第 场对 rating 的变化为 ，由于小 M 过于强大，怕惊吓到别人，所以可能会时不时打假赛，故意下分，所以可能是负的。

在参加所有比赛前，小 M 的当前 rating 和最大 rating 都是 。每打完一场比赛，小 M 的当前 rating 会对应变化（可能是负的，原因同上），如果超过的最大 rating，则最大 rating 会更新成当前 rating。

现在，由于小 M 会重塑时光，所以他能重排这 次比赛（假设 rating 变化值不变）。现在他想知道有多少种可能的最大 rating 更新的次数。

由于小 M 记忆力不好，所以会有 次修改操作，形如：

• 表示加入一个 rating 变化为 的比赛；
• 表示删除一个 rating 变化为 的比赛（保证至少存在一个变化为 的比赛）。

对于所有测试点保证：，，。

首先考虑将 Rating 变化从小到大排序可以得到最少的 Rating 变化次数，从大到小排序可以得到最多的 Rating 变化次数。

但是知道这一点似乎没什么用，毕竟你需要确定具体有几个 Rating 变化是可以到达的。

由于你可以对随意排列这个序列，一个想法就是考虑交换相邻的元素对最终结果的影响（即临项交换）。

考虑从最大值交换到最小值的过程，每次交换我们选择一个不再最后的上分场交换到后面。我们不妨假设在交换过程中最后一个 Rating 大小没有达到前面的顶峰。如果达到了，那么此时把前面的上分场全部移动到后面也不会改变答案，此时最高 Rating 的变化次数肯定等于最小值。

考虑此时交换两个数意味着什么。

• 交换之后，打完上分场仍然是顶峰。那么显然最大 Rating 的变化次数就不会改变。
• 交换之后，打完上分场没有到顶峰，那么最大 Rating 变化次数会减少 。
• 本来打完上分场就已经不是顶峰了，那么交换之后显然最大 Rating 变化也不会改变。

注意到整个过程答案的变化量最多为 ，而一开始答案是最大值，之后就变成最小值了，因此答案在交换过程中一定覆盖了其中的每一个点。

当然这道题直接构造其实也不难构造。模拟赛时突然想到了这个做法于是就在这里记录一下（通灵了）。

此时维护最大最小值即可。

最大值其实就是正数的个数，最小值就是所有负数求和，根据贪心策略不难发现把上分少的场次排在前面可以使得最大 Rating 变化更少。权值线段树二分即可。