Codeforces #312 Div2 E. A Simple Task

TLE5秒だけど、1秒もかからなかった。
http://codeforces.com/contest/558/problem/E

問題

英小文字だけで構成された長さLの文字列Sがある。
このSに対し以下のクエリQ個を順に処理した文字列を答えよ。

• 各クエリは区間[L,R]と昇順降順からなる。そこでSの部分S[L..R]を昇順または降順で並べ替える。

解法

自分の解法では、文字列をランレングス風に(始点,文字)のpairのsetで表現した。
各クエリではS[L..R]に対応するpairがいくつか求められるので、a～zの数を求めて並べ替えた。
並べ替えを行う内に、おおむね同じ文字が集まってset中のpairが少なくなることが期待できるので、計算量は問題ない。

別解法としては、a～zに対応した26個のsegtreeを使い、[L..R]中のa～zの数を求めたり設定したりしてもよい。
こちらは時間がかかるものの5sなら間に合うようだ。

int L,Q;
set<pair<int,char> > S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>L>>Q;
	cin>>s;
	char p='*';
	FOR(i,L) if(p!=s[i]) {
		p=s[i];
		S.insert({i,s[i]});
	}
	S.insert({L,'a'});
	
	while(Q--) {
		cin>>x>>y>>k;
		x--;y--;
		
		auto it=S.lower_bound({x,'a'});
		auto it2=S.lower_bound({y+1,'a'});
		if(it->first>x) it--;
		
		pair<int,char> ppre={-1,'*'}, ppost={-1,'*'};
		auto it3=it;
		int num[26]={};
		while(it3!=it2) {
			auto pre=it3++;
			int cnt=it3->first-pre->first;
			int n=0;
			if(pre->first<x) {
				cnt -= x-pre->first;
				ppre={pre->first,pre->second};
			}
			if(y+1<it3->first) {
				cnt -= it3->first - (y+1);
				ppost={y+1,pre->second};
			}
			
			num[pre->second-'a'] += cnt;
			S.erase(pre);
		}
		
		if(ppre.first>=0) S.insert(ppre);
		if(ppost.first>=0) S.insert(ppost);
		
		if(k==1) {
			FOR(i,26) if(num[i]) S.insert({x,'a'+i}), x += num[i];
		}
		else {
			for(i=25;i>=0;i--) if(num[i]) if(num[i]) S.insert({x,'a'+i}), x += num[i];
		}
	}
	
	auto it=S.begin();
	auto it2=it++;
	while(it!=S.end()) {
		FOR(i,it->first-it2->first) _P("%c",it2->second);
		it++;it2++;
	}
	_P("\n");
}

まとめ

ちょっとややこしいコード書いちゃったけど、通ってよかった。