自动搬运

查看原文

来自洛谷，原作者为

	SoundOfDestiny 这个家伙不懒，但还是什么都没有留下

搬运于2025-08-24 22:43:56，当前版本为作者最后更新于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;
    }
}