CF1862G The Great Equalizer

本题是一道关于序列操作的算法题，需要对给定的初始序列进行排序去重，并通过对数列中不同位置元素加上不同的常数来更新序列。具体实现可以使用 set 和 multiset 分别维护当前数列和相邻两数差距，进而求得最大的相邻两数差距作为总的操作次数。每次操作后输出数列中最大值加上操作次数的结果。

题目大意

有一台机器，他会对一个序列执行以下操作：

1. 对序列排序并去重
2. 如果序列中只剩下一个数，将它输出，结束操作
3. 对数列的第 $n,n-1,…,1$ 项加上 $1,2,…,n$，返回到第一步

给定一个初始序列，每次更改一个序列中元素的值（更改会一直保留）并输出当前序列放入机器中输出的结果。

思路

首先明确一点，数列中的最大项会在操作过程中一直是最大值，并且每次操作后将它加上 $1$，因此，最后输出的结果一定是数列中最大值加上操作次数，问题转变为求操作次数。

每次操作所产生的效果是相邻两数的差距缩小 $1$，当所有相邻两数差距都为 $0$ 时，操作结束。因此，总的操作次数应为相邻两数差距的最大值。

用 set 和 multiset 分别维护当前数列和相邻两数差距即可。

代码

int n, a[maxN + 5], aa[maxN + 5], q, idx, x;
set<int> ss;
map<int, int> num;
multiset<int> gap;
void mset_del(int x) {
    auto it = gap.lower_bound(x);
    if (it != gap.end())
        gap.erase(it);
}
void solve() {
    cin >> n;
    ss.clear(), num.clear(), gap.clear();
    //  gap.insert(0);
    rep(i, 1, n) {
        cin >> a[i];
        aa[i] = a[i];
        ss.insert(a[i]);
        num[a[i]]++;
    }
    sort(aa + 1, aa + 1 + n);
    rep(i, 2, n) gap.insert(aa[i] - aa[i - 1]);
    cin >> q;
    while (q--) {
        cin >> idx >> x;
        if (ss.size() == 1) {
            if (n == 1 || x == a[idx]) {
                num[a[idx]]--, num[x]++;
                ss.erase(a[idx]), ss.insert(x);
                cout << x << " ";

            } else {
                num[a[idx]]--, num[x]++;
                ss.insert(x);
                gap.insert(abs(x - a[idx]));
                cout << (*prev(ss.end()) + *prev(gap.end())) << " ";
            }
            a[idx] = x;
            continue;
        }
        if (--num[a[idx]] == 0) {
            auto it = ss.lower_bound(a[idx]);
            if (it == ss.begin()) {
                mset_del(*next(it) - *it);
            } else if (next(it) == ss.end()) {
                mset_del(*it - *prev(it));
            } else {
                mset_del(*next(it) - *it);
                mset_del(*it - *prev(it));
                gap.insert(*next(it) - *prev(it));
            }
            ss.erase(a[idx]);
        }
        if (++num[x] == 1) {
            ss.insert(x);
            auto it = ss.lower_bound(x);
            if (it == ss.begin()) {
                gap.insert(*next(it) - *it);
            } else if (next(it) == ss.end()) {
                gap.insert(*it - *prev(it));
            } else {
                mset_del(*next(it) - *prev(it));
                gap.insert(*next(it) - *it);
                gap.insert(*it - *prev(it));
            }
        }
        a[idx] = x;
        if (ss.size() == 1)
            cout << *ss.begin() << " ";
        else
            cout << (*prev(ss.end()) + *prev(gap.end())) << " ";
    }
    cout << endl;
}