Codeforces Round #312 Div2 E: A Simple Task

問題

codeforces.com

解法

[i文字目から][jの文字が][k個連続している]という同じ文字列が連続している区間の情報を保持しておく。

(start, end, d)というクエリに対して、startからendの中に入っている文字列の数を種類ごとに集計して、カウンティングソートする。
区間を割る形のクエリが来ても、そんなに面倒ではない。

コード

import java.util.ArrayList;
import java.util.Map.Entry;
import java.util.Scanner;
import java.util.TreeMap;

public class Main {

	public void solve() {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		int Q = scanner.nextInt();

		String string = scanner.next();

		TreeMap<Integer, Interval> treeMap = new TreeMap<>();
		for (int i = 0; i < N; i++) {
			treeMap.put(i + 1, new Interval(string.charAt(i) - 'a', 1));
		}

		for (int q = 0; q < Q; q++) {
			int qstart = scanner.nextInt();
			int qend = scanner.nextInt();
			int d = scanner.nextInt();
			int[] length = new int[26];

			Entry<Integer, Interval> headInterval = treeMap.lowerEntry(qstart);// startを含む区間を取り出す
			if (headInterval != null) {
				int start = headInterval.getKey();
				int kind = headInterval.getValue().kind;
				int num = headInterval.getValue().num;
				int end = start + num - 1;

				if (end <= qend) {
					if (end >= qstart) {
						length[kind] += start + num - qstart;// ソートに巻きこまれる文字列の数
						treeMap.put(start, new Interval(kind, qstart - start));
					}
				} else {
					// クエリで指定された区間が全て同じ文字だった場合スルーする
					continue;
				}
			}

			// ソートされる区間
			ArrayList<Integer> sortingKeys = new ArrayList<>(treeMap.subMap(
					qstart, qend + 1).keySet());
			for (Integer start : sortingKeys) {
				int kind = treeMap.get(start).kind;
				int num = treeMap.get(start).num;
				int end = start + num - 1;

				if (end > qend) {
					// endを含む区間だった時
					length[kind] += qend + 1 - start;
					treeMap.put(qend + 1, new Interval(kind, end - qend));
				} else {
					// 区間全体がソート対象の場合
					length[kind] += num;
				}

				// ソート対象になった区間は全て削除対象になる
				treeMap.remove(start);
			}

			// カウンティングソート
			if (d == 1) {
				// 昇順ソートの時
				int key = qstart;
				for (int j = 0; j < 26; j++) {
					if (length[j] != 0) {
						treeMap.put(key, new Interval(j, length[j]));
					}
					key += length[j];
				}
			} else {
				int key = qstart;
				for (int j = length.length - 1; j >= 0; j--) {
					if (length[j] != 0) {
						treeMap.put(key, new Interval(j, length[j]));
					}
					key += length[j];
				}
			}
		}
		scanner.close();

		// 出力
		StringBuilder sb = new StringBuilder();
		for (Entry<Integer, Interval> entry : treeMap.entrySet()) {
			for (int i = 0; i < entry.getValue().num; i++) {
				sb.append((char) ('a' + entry.getValue().kind));
			}
		}
		System.out.println(sb.toString());

	}

	public static void main(String[] args) {
		new Main().solve();
	}

}

class Interval implements Comparable<Interval> {
	int kind, num;

	public Interval(int k, int n) {
		this.kind = k;
		this.num = n;
	}

	@Override
	public int compareTo(Interval o) {
		if (this.kind == o.kind) {
			return this.num - o.num;
		}
		return this.kind - o.kind;
	}
}