AtCoder ARC #033 : C - データ構造

いつものCより易しめ。
http://arc033.contest.atcoder.jp/tasks/arc033_3

問題

初期状態で空の整数集合Sがある。
以下のQ個のクエリに答えよ。

1. Sに整数Xを加える。
2. S中でY番目に小さい数を求め、それを答えるとともにSから取り除く。

解法

Xは2*10^5とさほど多くないのでBITで処理する。

２つ目のクエリは、BITで総和がYとなる最少のXを二分探索で求めればよい。
そもそも自分はBITにlower_bound関数をつけてあるので、これを使うだけだった。

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	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;
	}
	V total(int e) {V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void update(int e, V val) {e++; while(e<=1<<ME) bit[e-1]+=val,e+=e&-e;}
};
BIT<int,21> bt;

int Q;
int T[202000],X[202000];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>Q;
	while(Q--) {
		cin>>x>>y;
		if(x==1) bt.update(y,1);
		else {
			j=bt.lower_bound(y);
			cout<<j<<endl;
			bt.update(j,-1);
		}
	}
}

まとめ

lower_boundはライブラリ化してあったけど、本番自分でまた二分探索書いちゃってた。