超絶苦手系。でもこういうのパッとできるようにせな。
問題概要
関数 があります。 はじめ、これは定数関数 です。
個のクエリが与えられるので、順番に処理してください。クエリは 2 種類あり、入力形式とクエリの内容は以下の通りです。
- 更新クエリ 1 a b: 2整数 が与えられるので、 として を で置き換える。
- 求値クエリ 2: の最小値を与える 、および の最小値を出力する。ただし、そのような が複数存在する場合には最小の を答える。
制約
考えたこと
まず は完全に無視してよいね。あとで一律に足せば OK。というわけなので問題は、
の最小値と、最小となる を求めよ
という問題になるわけだ。そしてこれは実は有名問題なのだ。実は が小さい順にソートされていると仮定したとき、その中央値 (メディアン) になるのだ。
これは今までなんども出題されて来た有名事実だけど、一応証明してみる。簡単のため は奇数とする。
このとき下図 () のように
が左側に寄っているときは、右へ動かすと の値を減らすことができる。例えば下図の上のケースの場合、 を だけ増やすと は 増えるが、他の項は ずつ減るので、全体で 減ることになる。
が右側に寄っているときも同様に、左へ動かすと の値を減らすことができる
ということがわかる。
このバランスがとれるのが、ちょうどメディアンの場合だ。
が偶数の場合はメディアンは 2 つあって、その間の区間内はすべて最小値になる。
いずれにしても問題は
更新クエリ: 要素 を追加する
求値クエリ: メディアンを求めよ (とそのときの の値)
ということに帰着された。
floating median
更新クエリと、 番目の値を求めるクエリとがオンラインに来る状態でも が固定ならば 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; } } }