けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 127 F - Absolute Minima (600 点)

超絶苦手系。でもこういうのパッとできるようにせな。

問題へのリンク

問題概要

関数  f(x) があります。 はじめ、これは定数関数  f(x)=0 です。

 Q 個のクエリが与えられるので、順番に処理してください。クエリは 2 種類あり、入力形式とクエリの内容は以下の通りです。

  • 更新クエリ 1 a b: 2整数  a, b が与えられるので、 g(x)=f(x)+|x−a|+b として  f(x) g(x) で置き換える。
  • 求値クエリ 2:  f(x) の最小値を与える  x、および  f(x) の最小値を出力する。ただし、そのような  x が複数存在する場合には最小の  x を答える。

制約

  •  1 \le Q \le 2 \times 10^{5}

考えたこと

まず  b は完全に無視してよいね。あとで一律に足せば OK。というわけなので問題は、


 |x - a_{0}| + |x - a_{1}| + \dots + |x - a_{n-1}| の最小値と、最小となる  x を求めよ


という問題になるわけだ。そしてこれは実は有名問題なのだ。実は  a_{0}, a_{1}, \dots, a_{n-1} が小さい順にソートされていると仮定したとき、その中央値 (メディアン) になるのだ。

これは今までなんども出題されて来た有名事実だけど、一応証明してみる。簡単のため  n は奇数とする。

このとき下図 ( n = 7) のように

  •  x が左側に寄っているときは、右へ動かすと  f(x) の値を減らすことができる。例えば下図の上のケースの場合、 x \epsilon だけ増やすと  |x - a_{0}| \epsilon 増えるが、他の項は  \epsilon ずつ減るので、全体で  5\epsilon 減ることになる。

  •  x が右側に寄っているときも同様に、左へ動かすと  f(x) の値を減らすことができる

ということがわかる。

f:id:drken1215:20190615113446p:plain

このバランスがとれるのが、ちょうどメディアンの場合だ。

f:id:drken1215:20190615113735p:plain

 n が偶数の場合はメディアンは 2 つあって、その間の区間内はすべて最小値になる。

f:id:drken1215:20190615114032p:plain

いずれにしても問題は


  • 更新クエリ: 要素  a を追加する

  • 求値クエリ: メディアンを求めよ (とそのときの  f(x) の値)


ということに帰着された。

floating median

更新クエリと、 K 番目の値を求めるクエリとがオンラインに来る状態でも  K が固定ならば 2 つの priority_queue で実現できる話は有名である。

メディアンであっても priority_queue でできる。

  • 小さい側半分を表すキュー (最大をとれるようにしておく)
  • 大きい側半分を表すキュー (最小をとれるようにしておく)

とを用意しておいて、両者の要素数を均衡させながら、値を入れ替えたりしていけば OK。これによって更新クエリを log オーダーでこなせる。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int MAX = 210000;
int Q;
long long type[MAX], a[MAX], b[MAX];

int main() {
    cin >> Q;

    long long sum = 0;
    priority_queue<long long> zen;
    priority_queue<long long, vector<long long>, greater<long long> > kou;
    long long zensum = 0;
    long long kousum = 0;
    
    for (int i = 0; i < Q; ++i) {
        cin >> type[i];
        if (type[i] == 1) {
            cin >> a[i] >> b[i];
            sum += b[i];

            if (zen.size() > kou.size()) {
                // kou に
                int t = zen.top();
                if (a[i] >= t) {
                    kou.push(a[i]); kousum += a[i];
                }
                else {
                    zen.pop(); zensum -= t;
                    zen.push(a[i]); zensum += a[i];
                    kou.push(t); kousum += t;
                }
            }
            else {
                // zen に
                if (zen.empty()) zen.push(a[i]), zensum += a[i];
                else {
                    int t = kou.top();
                    if (a[i] <= t) {
                        zen.push(a[i]); zensum += a[i];
                    }
                    else {
                        kou.pop(); kousum -= t;
                        kou.push(a[i]); kousum += a[i];
                        zen.push(t); zensum += t;
                    }
                }
            }
        }
        else {
            long long x = zen.top();
            long long res = (x * (int)zen.size() - zensum) + (kousum - x * (int)kou.size()) + sum;
            cout << x << " " << res << endl;
        }
    }
}