P8939 题解（2023 激励计划评分 7）

SoundOfDestiny · 2023-11-12 11:23:59 · 题解

分析

首先可以发现一个性质，当 p 单调不降时，\sum\limits_{i = 1}^{n}{|p_{i + 1} - p_i|} 可以取得最小值，这也很好理解。可以想象每个 p_i 都映射到数轴上，那么从最小的 p_i 出发再走回来至少要经过一个来回，即 \sum\limits_{i = 1}^{n}{|p_{i + 1} - p_i|} \geq 2 \cdot (\max{p} - \min{p}))，且一定可以取等。

那么我们只需要维护序列的极值即可，由于序列可能有重复，所以这里用 multiset 维护。

时间复杂度 O((n + q) \log{n})。

代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long

int n, q;
multiset<int> s;

signed main()
{
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
    cin >> n >> q;
    for (int i = 1, a; i <= n; i++)
        cin >> a, s.emplace(a);
    while (q--)
    {
        int op, x;
        cin >> op >> x;
        if (op == 1)
        {
            auto it = s.find(x);
            if (it == s.end())
            {
                cout << -1 << endl;
                continue;
            }
            s.erase(it);
        }
        else
            s.emplace(x);
        cout << (*(--s.end()) - *s.begin()) * 2 << endl;
    }
}