题目链接

https://atcoder.jp/contests/abc127/tasks/abc127_f

题意

初始时有个函数 $f(x) = 0$,现在有 $Q$ 个询问,询问有两种:

1 a b:令 $f(x) = f(x) + |x-a| + b$

2:求 $x$ 使得 $f(x)$ 最小,并求出这个 $f(x)$ 的最小值

题解

$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$。

images

插入新值的时候,就和当前中位数比较一下,如果小于等于中位数就插入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();
        }
    }
}

其他例题(TODO)

  1. https://www.luogu.com.cn/problem/P3644