Codeforces #530 Div1 D. Eels

こちらは解法を聞いてしまえば非常にシンプル。
https://codeforces.com/contest/1098/problem/D

問題

N匹のウナギの集合がおり、それぞれのサイズをS[i]とする。
ウナギは共食いを(N-1)回行い、最終的に1匹になる。

ウナギは共食いをすると、大きい方が小さい方を吸収し、大きさは両者の和となる。
その際、両者のサイズの差が２倍以下だと、危険な戦いが生じる。

ここでQ個のクエリが与えられる。
各クエリでは、ウナギを１匹取り除くまたは追加するという作業が行われる。
各作業後のウナギの集合について、共食いが生じたとき危険な戦いは何度生じるか答えよ。

解法

まずクエリは置いておいて、ウナギの集合のうち危険な戦いが生じるケースを考える。
ウナギのサイズSを昇順に並べたとする。
ウナギの小さい方同士が共食いを繰り返す場合を考えると、sum(S[0...i])*2＜S[i+1]であるとき、0～i番が互いに共食いしたウナギと、(i+1)番のウナギの共食いでは危険な戦いが生じない。

よって、(ウナギの数-1)から、sum(S[0...i])*2＜S[i+1]となるiを数え上げれば解となる。
これだが、容易に数えることができる。
複数のmultisetを容易する。j番のmultisetには、*1で済む。

int Q;
int num;
multiset<int> S[32];
ll sum[32];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d",&Q);
	while(Q--) {
		char C[10];
		scanf("%s%d",&C,&x);
		y=0;
		while(x>=(1<<(y+1))) y++;
		
		if(C[0]=='+') {
			S[y].insert(x);
			sum[y]+=x;
			num++;
		}
		else {
			S[y].erase(S[y].find(x));
			sum[y]-=x;
			num--;
		}
		
		int ret=num;
		ll tot=0;
		FOR(i,31) if(S[i].size()) {
			if(2*tot<*S[i].begin()) ret--;
			tot+=sum[i];
		}
		cout<<ret<<endl;
		
	}
}

まとめ

あるいみバケットソートっぽいね。

*1:2^j)-1)～(2^j)の大きさのウナギが入るとする。 sum(S[0...i])*2＜S[i+1]が生じるケースは、j番のmultisetに入る最小のウナギが、(j-1)番以下のmultisetに入るウナギの重さの総和の２倍超である場合のみである。 よって、判定を行うべきウナギを高々30個に絞ることができるので、クエリ毎に30個のmultisetの最小値を追うとしてO(Q log^2(S