Codeforces #247 Div2 E. Chemistry Experiment

問題文がちょっとわかりにくいな。
http://codeforces.com/contest/431/problem/E

問題

N個の試験管があり、それぞれ初期状態としてH[i]リットルの水銀が入っている。
この状態に対し、以下の２種類のクエリ計Q個に答えよ。

1. p[i]番目の試験管の中身をx[i]リットルの水銀にする。
2. 試験管全体に計V[i]リットルの水を入れると仮定する。この時、各試験管の水と水銀の合計体積の最小値が最大となるよう水を振り分けたい。水と水銀が両方入った試験管の合計体積を答えよ。(なお、実際に水は加えない。すなわち試験管の中身の体積は変化しない)

解法

２つ目のクエリがわかりにくいが、これは以下のように言い換えられる。
「試験管を水銀の体積順に昇順ソートする。N本中下位M本が同体積となるよう水を入れると、(M+1)本目の試験管の水銀の体積未満となるようなM本を選び、水と水銀の合計体積を答えよ」

試験管の数N<=10^5であり、１番のクエリを行うたびに昇順ソートを行うとTLEする。
以下のコードでは、各試験管の水銀の量を平方分割することで計算量を減らした。

なお、他の回答者の解法ではBITを２つ使う方式が目立つようだ。

int N,Q;
ll H[100001];
ll tot,ma;
vector<int> VV[1001];
ll bucket[1001];

const int SP=300;
void solve() {
	int f,i,j,k,l,x,y;
	
	vector<pair<int,int> > VP;
	cin>>N>>Q;
	FOR(i,N) {
		cin>>H[i];
		VP.push_back(make_pair(H[i],i));
	}
	sort(VP.begin(),VP.end());
	FOR(i,N) {
		VV[i/SP].push_back(VP[i].first);
		bucket[i/SP]+=VP[i].first;
	}
	
	FOR(i,Q) {
		cin>>j;
		if(j==1) {
			cin>>x>>y;
			x--;
			FOR(k,1000) {
				if(H[x]<=VV[k].back()) break;
			}
			bucket[k]-=H[x];
			FOR(j,VV[k].size()) {
				if(VV[k][j]==H[x]) {
					VV[k].erase(VV[k].begin()+j);
					break;
				}
			}
			
			if(VV[k].empty() || VV[k].size()+VV[k+1].size()<=SP) {
				ITR(it,VV[k+1]) VV[k].push_back(*it);
				bucket[k]+=bucket[k+1];
				VV[k+1].clear();
				bucket[k+1]=0;
				for(j=k+1;j<999;j++) {
					swap(VV[j],VV[j+1]);
					swap(bucket[j],bucket[j+1]);
				}
			}
			
			
			H[x]=y;
			FOR(j,999) {
				if(VV[j+1].empty() || y<VV[j+1].front()) break;
			}
			VV[j].push_back(y);
			sort(VV[j].begin(),VV[j].end());
			bucket[j]+=y;
			if(VV[j].size()>=2*SP) {
				for(k=999;k>j;k--) {
					swap(bucket[k],bucket[k+1]);
					swap(VV[k],VV[k+1]);
				}
				VV[j+1].clear();
				bucket[j+1]=0;
				for(k=SP;k<VV[j].size();k++) {
					VV[j+1].push_back(VV[j][k]);
					bucket[j+1]+=VV[j][k];
					bucket[j]-=VV[j][k];
				}
				VV[j].resize(SP);
			}
		}
		else {
			ll v,nc=0,tot=0;
			cin>>v;
			
			FOR(j,1000) {
				if(VV[j].empty()) {
					_P("%.12lf\n",(v+tot)/(double)N);
					break;
				}
				ll nc2=nc+VV[j].size(),tot2=tot+bucket[j];
				if(!VV[j+1].empty() && (v+tot2)> VV[j+1][0]*nc2) {
					tot=tot2;
					nc=nc2;
					continue;
				}
				
				FOR(x,VV[j].size()) {
					if(nc && (v+tot)<=VV[j][x]*nc) break;
					tot+=VV[j][x];
					nc++;
				}
				_P("%.12lf\n",(v+tot)/(double)nc);
				break;
			}
			out:
			;
		}
	}
	
}

まとめ

BIT2つの方がコードがシンプルだな…。