Codeforces #220 Div2. D. Inna and Sequence

ライブラリ構築問題…？
http://codeforces.com/contest/374/problem/D

問題

自然数からなる単調増加な数列Aが与えられる。

また、それとは別に、初期状態が空の数列Wがある。
ここで、以下のクエリをM個処理する。

• Wの末尾に0を加える
• Wの末尾に1を加える
• Wの要素のうち、数列Aに含まれる番号に相当する位置の要素を削除する

全クエリを処理した後のWの中身を答えよ。

解法

自分は以下の通りクエリを２周回して解答した。

1. 1周目では、要素数だけを計算する。
   • 追加クエリは普通にWに追加する。
   • 削除クエリが来たとき、実際にWの要素は削除せず、Wのうち有効な要素数だけ覚えておいてその数を用いて数列Aのlower_boundを取り削除される数を調べる
2. ２周目で削除クエリを再度処理する。
   • BITを使い、Wの各要素に対応したindexに対し、有効なら1、無効なら0を埋める。初期状態は全部1。
   • あるクエリについてW中A[i]番の要素を削除する場合、BITの合計値がA[i]となる最小のindexを求めて、その要素を0(無効)にする。

最後に有効な要素のみ列挙する。

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	BIT(){clear();};
	void clear() {ZERO(bit);};

	int lower_bound(V val) {
		V tv=0;
		int i,ent=0;
		FOR(i,ME) if(tv+bit[ent+(1<<(ME-1-i))-1]<val) tv+=bit[ent+(1<<(ME-1-i))-1], ent += (1<<(ME-1-i));
		return ent;
	}
	V total(int entry) {
		V s=0;
		entry++;
		while(entry>0) s+=bit[entry-1], entry -= entry & -entry;
		return s;
	}
	void update(int entry, V val) {
		entry++;
		while(entry <= (1<<ME)) bit[entry-1] += val, entry += entry & -entry;
	}
};
BIT<int,20> bt;

int N,M;
int A[1000002],B[1000002];
int NG[1000002];
vector<int> V,D;

void solve() {
	int f,i,j,k,l,x,y,r;
	
	cin>>N>>M;
	FOR(i,M) cin>>A[i];
	A[M]=N;
	NG[0]=1;
	y=0;
	V.push_back(2);
	
	FOR(i,N) bt.update(i+1,1);
	
	FOR(i,N) {
		cin>>x;
		if(x>=0) V.push_back(x),y++;
		else {
			f = lower_bound(A,A+M,y+1) - A;
			if(f>0) {
				D.push_back(f);
				y-=f;
			}
		}
	}
	
	if(y==0) {
		_P("Poor stack!\n");
	}
	else {
		FOR(i,D.size()) {
			for(f=D[i]-1;f>=0;f--) {
				j = bt.lower_bound(A[f]);
				NG[j]=1;
				bt.update(j,-1);
			}
		}
		FOR(i,V.size()) if(NG[i]==0) _P("%d",V[i]);
		_P("\n");
	}
}

まとめ

BITで得られる合計値に対し、lower_boundを取る仕組みがなかったので今回ライブラリに加えた。
合計値が単調増加でないと使えないけどね。