Codeforces #452 Div2 F. Letters Removing

またsetゴリ押しゲー。
http://codeforces.com/contest/899/problem/F

問題

文字列Sと、M個のクエリが与えられる。

クエリは文字列における区間[L,R]と1文字が与えられるので、文字列Sより区間内における指定文字を取り除こう。
最終的に残る文字列は何か。

解法

まず、文字の種類別にsetを保持し、indexを登録しよう。

以後、文字列数分の要素を持つBITを用いる。
初期状態では各要素1で、文字列から文字が取り除かれたらその要素を0にすることを考える。
さて、クエリにおける区間[L,R]が与えられると、このBITを二分探索することで区間[L,R]が初期のSにおけるどの部分に該当するかがわかる。
よって最初に作成したsetを探索してその区間のindexを取り除いていこう。

indexを取り除く回数は高々O(|S|)なので、全体でもO(|S|+Mlog^2|S|)程度の計算量で済む。

int N,M;
string S;
set<int> C[128];

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


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>S;
	FOR(i,N) {
		C[S[i]].insert(i);
		bit.add(i,1);
	}
	
	while(M--) {
		int L,R;
		char c;
		cin>>L>>R>>c;
		L=bit.lower_bound(L);
		R=bit.lower_bound(R);
		
		while(1) {
			auto it=C[c].lower_bound(L);
			if(it==C[c].end() || *it>R) break;
			x=*it;
			bit.add(x,-1);
			C[c].erase(x);
		}
	}
	
	FOR(i,N) {
		if(C[S[i]].count(i)) cout<<S[i];
	}
	cout<<endl;
	
}

まとめ

似たようなデータ構造ゲー２連発は勘弁。