题解 ARC153B【Grid Rotations】

一次操作是把四个子矩形分别旋转 \(180^\circ\)。不难发现，可以横纵坐标分别考虑，则该操作变为横坐标的两段区间分别翻转、纵坐标的两段区间分别翻转。

区间翻转操作、最后输出数列是 文艺平衡树 的基本操作，搞两棵平衡树维护即可。

时间复杂度 \(\Theta(nm+(n+q)\log n+(m+q)\log m)\)。

实际上有解法可以做到 \(\Theta(nm+q)\)，但本解法足以通过本题。

// Problem: B - Grid Rotations
// Contest: AtCoder - AtCoder Regular Contest 153
// URL: https://atcoder.jp/contests/arc153/tasks/arc153_b
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const int N = 5e5+5;

int n, m, q;
vector<int> ppr, ppc;
vector<string> s;
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
struct Node {
	int val, rnd, sz, lc, rc, rev;
	Node(int a=0, int b=0) : val(a), rnd(rand()), sz(b), lc(0), rc(0), rev(0) {}
	~Node() {}
};
struct FHQTreap {
	Node t[N];
	int sz, rt, L, M, R;
	int newNode(int x) {
		t[++sz] = Node(x, 1);
		return sz;
	}
	void pushup(int u) {
		t[u].sz = t[t[u].lc].sz + t[t[u].rc].sz + 1;
	}
	void pushdown(int u) {
		if(!t[u].rev) return;
		if(t[u].lc) t[t[u].lc].rev ^= 1;
		if(t[u].rc) t[t[u].rc].rev ^= 1;
		swap(t[u].lc, t[u].rc);
		t[u].rev = 0; 
	}
	void split(int u, int lim, int& x, int& y) {
		if(!u) x = y = 0;
		else {
			pushdown(u);
			if(t[t[u].lc].sz < lim) {
				x = u;
				split(t[u].rc, lim-t[t[u].lc].sz-1, t[u].rc, y);
			}
			else {
				y = u;
				split(t[u].lc, lim, x, t[u].lc);
			}
			pushup(u);
		}
	}
	int merge(int u, int v) {
		if(!u || !v) return u | v;
		if(t[u].rnd < t[v].rnd) {
			pushdown(u);
			t[u].rc = merge(t[u].rc, v);
			pushup(u);
			return u;
		}
		else {
			pushdown(v);
			t[v].lc = merge(u, t[v].lc);
			pushup(v);
			return v;
		}
	}
	void reverse(int l, int r) {
		split(rt, l-1, L, R);
		split(R, r-l+1, M, R);
		t[M].rev ^= 1;
		rt = merge(L, merge(M, R));
	}
	void get(int u, vector<int>& a) {
		pushdown(u);
		if(t[u].lc) get(t[u].lc, a);
		a.push_back(t[u].val);
		if(t[u].rc) get(t[u].rc, a);
	}
}pr, pc;

int main() {
	scanf("%d%d", &n, &m);
	s.resize(n);
	rep(i, 0, n-1) cin>>s[i];
	rep(i, 0, n-1) pr.rt = pr.merge(pr.rt, pr.newNode(i));
	rep(j, 0, m-1) pc.rt = pc.merge(pc.rt, pc.newNode(j));
	for(scanf("%d", &q); q; q--) {
		int x, y;
		scanf("%d%d", &x, &y);
		pr.reverse(1, x); pr.reverse(x+1, n);
		pc.reverse(1, y); pc.reverse(y+1, m);
	}
	pr.get(pr.rt, ppr);
	pc.get(pc.rt, ppc);
	rep(i, 0, n-1) {
		rep(j, 0, m-1) putchar(s[ppr[i]][ppc[j]]);
		puts("");
	}
	return 0;
}