CODE FESTIVAL 2017 Final,E: Combination Lock

https://cf17-final-open.contest.atcoder.jp/tasks/cf17_final_e

まず区間の真ん中をまたぐ部分は考えなくていいです。
すると区間は左or右に寄った形になりますが、右にある区間を左に移しても問題ありません。
よって左半分に操作を行って右半分の文字列に一致させる問題になりました。

さらに
[l, r],[l, r'](r < r')のような2つの区間は[l, r],[r, r']と言い換えられます。
これを適用することで、すべての[l, r]について、あるlに対してはrが１つのみ対応する形になります。
setをmergeしていくunionfindを使えばO(N(logN)^2)でこの形を求めることができます。

ここまでできればあとはBITを使って端から文字列を一致させていけばいいです。

割と実装重かったけどそんなにてこずらなくてよかった。

int N, Q;
int A[MAX_N];
vector<int> G[MAX_N];
int to[MAX_N];
BIT bit;

struct mergeUF { //O((logn)^2)
	int n;
	vector<set<int>> g;
	vector<int> gat;

	int find(int p) {
		if(gat[p] == p) return p;
		else return gat[p] = find(gat[p]);
	}

	void init() {
		n = N / 2 + 1;
		g.resize(n); gat.resize(n);
		rep(i, 0, n) {
			rep(j, 0, sz(G[i])) {
				int v = G[i][j];
				g[i].insert(v);
			}
			gat[i] = i;
		}
	}


	void unite(int x, int y) {
		int a = find(x), b = find(y);
		if(a == b) return;
		if(sz(g[a]) > sz(g[b])) swap(a, b);
		gat[a] = b;

		for(int s : g[a]) {
			g[b].insert(s);
		}
		g[a].clear();
	}

	bool same(int x, int y) { return find(x) == find(y); }
} uf;


void solve() {
	string str;
	cin >> str;
	N = sz(str);
	rep(i, 0, N) A[i] = str[i] - 'a';

	cin >> Q;
	rep(i, 0, Q) {
		int a, b;
		cin >> a >> b; a--; b--;
		int m1 = (N - 1) / 2, m2 = N / 2;
		if(a <= m1 && m2 <= b) {
			if(m1 - a <= b - m2) a = N - 1 - a + 1;
			else b = N - 1 - b - 1;
		}
		if(a >= m2) {
			int ta = a, tb = b;
			a = N - 1 - tb;
			b = N - 1 - ta;
		}
		b++;
		if(b > a) G[a].pb(b);
	}

	uf.init();
	bit.init(N / 2 + 10);

	rep(i, 0, N / 2) bit.update(i, i + 1, A[i]);
	memset(to, -1, sizeof(to));

	rep(i, 0, N / 2) {
		int a = uf.find(i);
		if(uf.g[a].empty()) continue;
		auto it = uf.g[a].begin();
		int tmp = *it;
		to[i] = tmp;
		uf.g[a].erase(it);
		uf.unite(i, tmp);
	}

	rep(i, 0, N / 2) {
		int a = bit.get(i, i + 1) % 26, b = A[N - 1 - i] % 26;
		if(to[i] == -1) {
			if(a != b) {
				cout << "NO\n";
				return;
			}
		}
		else {
			int t = (b - a + 26) % 26;
			bit.update(i, to[i], t);
		}
	}
	cout << "YES\n";

}

想定解はまず累積和をかんがえて、区間の端を+1-1する操作に言い換えています。これは思いつきたかった。
そこからがすごい頭良くて感心しました(こなみかん)