ABC127 F - Absolute Minima (600)

F - Absolute Minima

概要

関数f(x)が与えられる。関数f(x)は最初f(x) = 0の定数関数である。
クエリがQ個与えられるので、それに従い操作する。クエリは下記2つ。

• 更新クエリ："1 a b"の形で与えられ、f(x) <- f(x) + |x - a| + bと置き換える
• 求値クエリ："2" の形で与えられ、f(x)の最小値をとる最も小さなxと、f(x)の最小値を出力する

制約

1 ≦ Q ≦ 2 *10^5
-10^9 ≦ a, b ≦ 10^9

方針

実験すると、n回の更新クエリののちにf(x)の最小値をとるxは、aを小さい順に並べてnが偶数ならn/2番目, nが奇数なら(n-1) / 2 + 1番目のaで実現される。これはaの中央値である。

中央値を管理してゆくやり方の1つとして、priority_queueを2つ使う方法がある。
最大値を返すmpqと最小値を返すppqを準備し、mpq.size() ≧ ppq.size(), mpq.top() ≦ ppq.top() を維持するようにaを格納してゆく。

また、f(x)の値を求める際は、上記aの中央値をamとすると、f(x) = Σ|x - a| + Σbのうちの|x-a|の和について、a ≦ amなるaについては(am - a)を足し、a>amなるaについては(a - am)を足せばよい。これは各priority_queueに入っている要素の和をpriority_queueといっしょに管理していけばよい。Σbはamの選び方によらないので、単純に和をもっておけばよい。

感想

けんちょんさんのブログを参考にしました。
drken1215.hatenablog.com

また、中央値とその範囲和の管理はBITでもできるようです。
アルメリアさんのブログに詳細があります。
betrue12.hateblo.jp

解答

Submission #6600928 - AtCoder Beginner Contest 127

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int Q;
	cin >> Q;
 
	ll sm = 0;
 
	priority_queue<ll> mpq;
	priority_queue<ll, vector<ll>, greater<ll>> ppq;
	ll msm = 0;
	ll psm = 0;
 
	rep(_, Q){
		int u;
		cin >> u;
 
		if(u == 1){
			ll a, b;
			cin >> a >> b;
			sm += b;
 
			if(mpq.size() > ppq.size()){
				ll t = mpq.top();
				if(a >= t){
					ppq.push(a);
					psm += a;
				}else{
					mpq.pop();
					msm -= t;
 
					mpq.push(a);
					msm += a;
 
					ppq.push(t);
					psm += t;
				}
			}else{
				if(mpq.empty()){
					mpq.push(a);
					msm += a;
				}else{
					ll t = ppq.top();
					if(a <= t){
						mpq.push(a);
						msm += a;
					}else{
						ppq.pop();
						psm -= t;
 
						ppq.push(a);
						psm += a;
 
						mpq.push(t);
						msm += t;
					}
				}
			}
		}else{
			ll x = mpq.top();
			ll res = (x * (ll)mpq.size() - msm) + (psm - x * (ll) ppq.size()) + sm;
			cout << x << " " << res << endl;
		}
 
	}
 
}