题解 [ARC153B] Grid Rotations

[ARC153B] Grid Rotations

有思维含量的一题。

我们横纵坐标分开考虑，对于每一个矩形，每次操作会使其内部元素的横坐标上下对调。

纵坐标也同理，左右对调。

而这种反转操作我们显然可以直接用两棵文艺平衡树维护，复杂度 \(O(n\log n)\)。

标程的做法更巧妙一下。我们可以把一条链收尾相接，两段序列的反转就相当于圆的反转。

所以我们可以只定位其中两个点，然后根据其最终位置填补出剩下元素。复杂度 \(O(n)\)。

代码是第一种做法。

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n, m, q, a[N], b[N], rt = 0, x[N], y[N], tot = 0;
char c[N];
struct node{
	int l, r, siz, v, lazy, pri;
}t[N];
int d(int i, int j) {
	return (i - 1) * m + j;
}
void add(int x) {t[x].v = x; t[x].pri = rand(); t[x].siz = 1; t[x].l = t[x].r = 0;}
void pushdown(int id) {
	if (t[id].lazy == 0) return;
	swap(t[id].l, t[id].r);
	t[t[id].l].lazy ^= 1;
	t[t[id].r].lazy ^= 1;
	t[id].lazy = 0;
}
void pushup(int id) {
	t[id].siz = t[t[id].l].siz + t[t[id].r].siz + 1;
}
void split(int id, int k, int &l, int &r) {
	if (id == 0) {
		l = r = 0;
		return;
	}
	pushdown(id);
	int tmp = t[t[id].l].siz + 1;
	if (tmp <= k) {
		l = id;
		split(t[id].r, k - tmp, t[id].r, r);
	} else {
		r = id;
		split(t[id].l, k, l, t[id].l);
	}
	pushup(id);
}
int merge(int l, int r) {
	if (!l || !r) return l + r;
	if (t[l].pri < t[r].pri) {
		pushdown(l);
		t[l].r = merge(t[l].r, r);
		pushup(l);
		return l;
	} else {
		pushdown(r);
		t[r].l = merge(l, t[r].l);
		pushup(r);
		return r;
	}
}
void dfs1(int u) {
	pushdown(u);
	if (t[u].l) dfs1(t[u].l);
	x[++tot] = t[u].v;
	if (t[u].r) dfs1(t[u].r);
}
void dfs2(int u) {
	pushdown(u);
	if (t[u].l) dfs2(t[u].l);
	y[++tot] = t[u].v;
	if (t[u].r) dfs2(t[u].r);
}
void huan(int l, int r) {
	int t1, t2, t3, tt;
	split(rt, r, t1, t2);
	split(t1, l - 1, t1, t3);
	t[t3].lazy ^= 1;
	rt = merge(merge(t1, t3), t2);
}
int main() {
	srand(time(0));
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			cin >> c[d(i, j)];
		}
	}
	for (int i = 1; i <= n; ++i) {
		add(i);
		rt = merge(rt, i);
	}
	cin >> q;
	for (int i = 1; i <= q; ++i) {
		cin >> a[i] >> b[i];
		huan(1, a[i]); huan(a[i] + 1, n);
	}
	dfs1(rt);
	rt = tot = 0;
	for (int i = 1; i <= m; ++i) {
		add(i);
		rt = merge(rt, i);
	}
	for (int i = 1; i <= q; ++i) {
		huan(1, b[i]); huan(b[i] + 1, m);
	}
	dfs2(rt);
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			cout << c[d(x[i], y[j])];
		}
		cout << endl;
	}
	return 0;
}