AtCoder ABC #127 : F - Absolute Minima

簡潔な解法と、書き馴れた解法どっちがいいのかね。
https://atcoder.jp/contests/abc127/tasks/abc127_f

問題

初期状態で1変数関数f(x)=0がある。
以下のクエリに順次答えよ。

• 整数Ai,Biが与えられるので、f(x)をf(x) + |x-Ai| + Biで置き換える。
• f(x)の最小値とその時のxの値を答えよ。

解法

後者のクエリについて、Biの部分は合計を考えればよいだけ。
後はそれまで出てきたAiについて、|x-Ai|の和の最小値を求めればよい。
この形は頻出で、最小となるにはxがAiの中央値を取ればよい。

自分はAiを座標圧縮したうえで登場回数とAiの総和をそれぞれBITで持った。
前者で二分探索すると中央値が特定できxが定まるので、あとは後者を使って|x-Ai|の和を高速に求める。

なお、配列の要素が1個ずつ増える場合の中央値管理には、priority_queueやmultisetを2つ持って前半と後半の要素を分けて格納するようにし、常に両者の個数を均等化するようにする、というテクもあるようだ。

int Q;

int T[202020],A[202020],B[202020];
ll S[202020];
vector<ll> As;

template<class V, int ME> class BIT {
public:
	V bit[1<<ME],val[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { val[e++]+=v; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
	void set(int e,V v) { add(e,v-val[e]);}
	int lower_bound(V val) {
		V tv=0; int i,ent=0;
		for(i=ME-1;i>=0;i--) if(tv+bit[ent+(1<<i)-1]<val) tv+=bit[ent+(1<<i)-1],ent+=(1<<i);
		return ent;
	}
};
BIT<ll,20> num,tot;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>Q;
	As.push_back(-1<<30);
	As.push_back(1<<30);
	
	for(i=1;i<=Q;i++) {
		cin>>T[i];
		if(T[i]==1) {
			cin>>A[i]>>B[i];
			As.push_back(A[i]);
		}
		S[i]=S[i-1]+B[i];
	}
	
	sort(ALL(As));
	As.erase(unique(ALL(As)),As.end());
	for(i=1;i<=Q;i++) {
		if(T[i]==1) {
			A[i]=lower_bound(ALL(As),A[i])-As.begin();
			num.add(A[i],1);
			tot.add(A[i],As[A[i]]);
		}
		else {
			x=num(1<<19);
			y=(x+1)/2;
			r=num.lower_bound(y);
			ll ret=S[i];
			y=num(r-1);
			ll su=tot(r-1);
			ret+=1LL*y*As[r]-su;
			y=num(1<<19)-num(r);
			ret+=tot(1<<19)-tot(r)-1LL*y*As[r];
			cout<<As[r]<<" "<<ret<<endl;
		}
	}
	
}

まとめ

こういうのoff-by-oneミスやらかしそうで怖いんだよね。