Codeforces 240 F TopCoder

問題

英小文字からなる文字列sが与えられる。
この文字列に対して、以下のようなクエリをm個実行する。


入力l, rを受け取る。
sのl文字目からr文字目を、その部分が回文になるように並び替える。
回文が複数個できる場合は、辞書順で最小になるように並び替える。
回文を作れない場合は、何もしない。


クエリを全て実行し終えた時点での文字列sを出力せよ。

制約条件

文字列の長さn≦10^5
クエリの個数m≦10^5
各クエリのl, rは1以上n以下

方針

a〜zのアルファベットごとにsegment treeを作る。
セグメント木で区間[i, j]に含まれるアルファベットの個数を高速に求められるようにしておく。
また、区間[i, j]に対して、データを高速に一様に変更できるようにする。


これは、セグメント木の接点ごとに、全てのデータが同一かのフラグを持つことで出来る。


segment木が作れたら、
l〜rの範囲で各アルファベットの個数を数えれば、
aの文字が何文字目から何文字目にくるか、
bの文字が……というのがわかるので、
segtreeを一様にアルファベットごとに変更すればいい。


TLEが厳しく、segtreeを読み書きする関数にinlineをつけるなどしたら通った。

ソースコード

const int MX = 131072;
int dat[26][MX * 2 - 1];
int same[26][MX * 2 - 1];
char in[MX];

int N;
inline void set(int c, int a, int b, int k, int l, int r, int x){
	if(r <= a || b <= l) return;
	if(a <= l && r <= b){
		same[c][k] = x;
		dat[c][k] = (r - l) * x;
		return;
	}
	if(same[c][k] >= 0){
		same[c][k * 2 + 1] = same[c][k * 2 + 2] = same[c][k];
		dat[c][k * 2 + 1] = dat[c][k * 2 + 2] = same[c][k] * (r - l) / 2;
		same[c][k] = -1;
	}
	set(c, a, b, k * 2 + 1, l, (l + r) / 2, x);
	set(c, a, b, k * 2 + 2, (l + r) / 2, r, x);
	dat[c][k] = dat[c][k * 2 + 1] + dat[c][k * 2 + 2];
}
inline int get(int c, int a, int b, int k, int l, int r){
	if(r <= a || b <= l) return 0;
	if(same[c][k] >= 0) return (min(r, b) - max(l, a)) * same[c][k];
	if(a <= l && r <= b) return dat[c][k];
	return get(c, a, b, k * 2 + 1, l, (l + r) / 2) +
		get(c, a, b, k * 2 + 2, (l + r) / 2, r);
}

void run()
{
	int n, m;
	scanf("%d%d%s", &n, &m, in);
	for(N = 1; N < n; N *= 2);
	rep(i, n) set(in[i] - 'a', i, i + 1, 0, 0, N, 1);
	rep(i, m){
		int l, r, cnt[26];
		scanf("%d%d", &l, &r);
		l--;
		
		rep(j, 26) cnt[j] = get(j, l, r, 0, 0, N);
		
		int o = -1, t = 0;
		rep(j, 26) if(cnt[j] % 2){
			o = j;
			t++;
		}
		
		if((r - l) % 2 && t != 1 || (r - l) % 2 == 0 && t != 0) continue;
		
		rep(j, 26) set(j, l, r, 0, 0, N, 0);
		if(o >= 0){
			set(o, l + (r - l) / 2, l + (r - l) / 2 + 1, 0, 0, N, 1);
			cnt[o]--;
		}
		
		rep(j, 26) if(cnt[j]){
			set(j, l, l + cnt[j] / 2, 0, 0, N, 1);
			set(j, r - cnt[j] / 2, r, 0, 0, N, 1);
			l += cnt[j] / 2;
			r -= cnt[j] / 2;
		}
	}
	rep(i, n){
		int cnt = 0;
		rep(j, 26) if(get(j, i, i + 1, 0, 0, N)){
			in[i] = 'a' + j;
			break;
		}
	}
	puts(in);
}