Codeforces 431(#245 Div2 only) E. Chemistry Experiment

Codeforces データ構造

問題

n個の水銀の入ったチューブがあり、i番目にはh[i]リットルの水銀が入っている。
このとき次のクエリに答えよ。

1 pi vi : pi番目のチューブの水銀の量をviにする。
2 xi : 合計viリットルの水を好きなようにチューブに入れる。使ったチューブのうち最大の水＋水銀の量を最小にしたい。この最小値を求めよ。このクエリで入れた水は即出す。（水銀は変化しない）

制約条件

n≦10^5
h[i], vi≦10^9
xi≦10^15

方針

チューブは水銀の量が少ない順に使い、水面の高さが均等になるようにすればよい。
ギザギザの階段状の容器にxリットルの水を入れたときの水面の高さを求める問題になる。


これは階段の何段目の手前に水面が来るかの二分探索でよい。
この二分探索をするために、水銀の少ない順にn個のチューブを使ったときの水銀の和を求める必要がある。その方法は以下の通り。


(水銀の量, インデックス)を座標圧縮。
今有効な(水銀の量, インデックス)のところを1、それ以外は0にする。
階段のi番目のインデックスを求めたいときはこの集合でi番目の1を求めればよいので、
binary indexed tree上の二分探索をすればよい。


i番目までの水銀の量の和も別のbinary indexed treeを持って管理する。
有効な水銀が切り替わったら、（a[i] = xからa[i] = yに変化したら）
有効なインデックスを管理するBITでは(x, id)を0に、(y, id2)を1にして
水銀の和のbinary indexed treeのほうではidからx引いて、idにyを足す。


全ての二分探索はbinary indexed tree上のなので、一回当たりのクエリは全てO(log n)で計算できる。


自分は最適な水面を作るチューブの個数三分探索 + 累積和の管理は何故か平衡二分探索木を使うとかいう壮絶に頭の悪いことをした。（疲れていた）
この場合、三分探索で想定水面より高い水銀のところに水を入れてはダメなので、予め二分探索をして使える水銀の限界を求めておく。

ソースコード

int n, q, a[100010];
ll in[100010][3];

int main(){
	vector<pi> v;
	scanf("%d%d", &n, &q);
	rep(i, n) scanf("%d", a + i), v.pb(pi(a[i], i));
	rep(i, q){
		scanf("%I64d%I64d", in[i], in[i] + 1);
		if(in[i][0] == 1){
			scanf("%I64d", in[i] + 2);
			v.pb(pi(in[i][2], n + i));
		}
	}
	v.pb(pi(-inf, inf));
	sort(all(v));
	BIT<int> bit(v.size() + 1);
	treap<ll> tree;
	
	rep(i, v.size()) tree.insert(i, 0);
	rep(i, n){
		a[i] = lower_bound(all(v), pi(a[i], i)) - v.begin();
		bit.add(a[i], 1);
		tree.add(a[i], v[a[i]].first);
	}
	rep(i, q){
		if(in[i][0] == 1){
			int idx = in[i][1] - 1, x = lower_bound(all(v), pi(in[i][2], i + n)) - v.begin();
			bit.add(a[idx], -1);
			tree.add(a[idx], -v[a[idx]].first);
			bit.add(a[idx] = x, 1);
			tree.add(a[idx], v[a[idx]].first);
		}
		else{
			ll x = in[i][1];
			
			int L = 0, R = n + 1;
			while(L + 1 < R){
				int m = (L + R) / 2;
				int mi = bit.find(m);
				double s = tree.query(0, mi + 1);
				if(v[mi].first > EPS + (s + x) / m) R = m;
				else L = m;
			}
			int lo = 1, hi = L;
			
			while(lo + 2 < hi){
				int a = (lo * 2 + hi) / 3;
				int b = (lo + hi * 2) / 3;
				int ai = bit.find(a), bi = bit.find(b);
				
				double l = tree.query(0, ai + 1), r = tree.query(0, bi + 1);
				if((l + x) / a >= (r + x) / b) lo = a;
				else hi = b;
			}
			double mn = INF;
			for(int j = lo; j <= hi; j++){
				int ii = bit.find(j);
				double s = tree.query(0, ii + 1);
				mn = min(mn, (s + x) / j);
			}
			printf("%.20f\n", mn);
		}
	}
	return 0;
}