Atcoder ABC 127F（对顶堆动态维护中位数）

$f(x)$ 必然长这样：$f(x) = |x-a_1| + |x-a_2| + … + |x-a_n| + \sum\limits_{i=1}^{n}b_i$

要让 $f(x)$ 最小，就令 $x$ 等于 $a_1,a_2,…,a_n$ 的中位数。

那么已知中位数 $a_k$ 的话，如何找到 $\sum\limits_{i=1}^{n} |a_k - a_i|$ ？

假设 $n$ 为奇数，那如果我们将 $a_i$ sort 一下，有：

$\sum\limits_{i=1}^{n} |a_{\frac{n+1}{2}} - a_i| = \sum\limits_{i=1}^{\frac{n}{2}}(a_{\frac{n+1}{2}+i} - a_{\frac{n+1}{2}-i})$

如果我们分开维护中位数 $a_{\frac{n+1}{2}}$ 左右两边的 sum 就可以 $O(1)$ 求和了！

用对顶堆！

我们维护两个 multiset<ll>，一个是大顶堆（叫做small），维护小于等于中位数的部分。一个是小顶堆（叫做big），小顶堆维护大于等于中位数的部分，并且保证两者的 size 之差 $\leq 1$。

插入新值的时候，就和当前中位数比较一下，如果小于等于中位数就插入small，否则插入big，然后看一下size之差，如果 size之差 $> 1$ 就从多的那个堆取出来，插入另外一个堆，这样就动态调整了中位数。

这样我们可以 $O(1)$ 求出中位数，并且 $\sum\limits_{i=1}^{n} |a_k - a_i|$ 也可以 $O(1)$ 得出，用big的$sum$ 减去 small的 $sum$ 即可。（写的时候需要讨论一下 size 之差为 1,0,-1 的三种情况）。

细节部分直接看代码吧。

using namespace std;
#include <bits/stdc++.h>

#define ll long long

const int mod = 1e9+7;
const int maxn = 1e3+5;
const int maxm = 2e5+10;

ll c = 0, ssum = 0, bsum = 0;
multiset<ll> big;
multiset<ll, greater<ll> > small;

void ins(ll a, ll b) {
    c += b;

    if (!small.size()) {
        ssum += a;
        small.insert(a); return;
    }

    if (a <= *small.begin()) {
        small.insert(a);
        ssum += a;
    } else {
        big.insert(a);
        bsum += a;
    }

    if (small.size() > big.size() + 1) {
        auto p = small.begin();
        bsum += *p, ssum -= *p;
        big.insert(*p);
        small.erase(p);
    }

    if (big.size() > small.size() + 1) {
        auto p = big.begin();
        bsumssum += *p;
        small.insert(*p);
        big.erase(p);
    }
}

void query() {

    ll ans = bsum
    if (small.size() == big.size()) {
        cout << *small.begin() << " " << ans << "\n";
        return;
    }

    if (small.size() == big.size() + 1) {
        ans += *small.begin();
        cout << *small.begin() << " " << ans << "\n";
        return;
    }

    if (big.size() == small.size() + 1) {
        ans -= *big.begin();
        cout << *big.begin() << " " << ans << "\n";
    }
}

int main() {
    fastio;

    int Q; cin >> Q;
    while (Q--) {
        int op; cin >> op;
        if (op == 1) {
            int a,b;
            cin >> a >> b;
            ins(a,b);
        } else {
            query();
        }
    }
}