有思维含量的一题。
我们横纵坐标分开考虑，对于每一个矩形，每次操作会使其内部元素的横坐标上下对调。
纵坐标也同理，左右对调。
而这种反转操作我们显然可以直接用两棵文艺平衡树维护，复杂度 \(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;
}