题意:

给你个 $1000 \times 1000$ 的矩阵,每次交换任意两个不重合的子矩阵,求最后的结果

如果你是一位数据结构学傻的选手(像我),那么第一感觉肯定是用平衡树做,复杂度 $O(m \times n \log n)$ ,不过不幸的是,由于常数巨大,最后得分甚至可能不如暴力的 memcpy

如果你是一个不会高级数据结构的普及选手你说不定就能想到链表。维护一个矩形的链表,然后每次交换就分别把两块矩阵取出再拼接上去。

彩蛋——在摸你赛中的题面:

之所以续走的那些香港记者,是因为他们掌握了长者钦点董先生的关键证据,现在这份证据落到了你的手里。这份文件是一个 $n \times m$ 的矩形,矩形内每一个元素是一个字符串。这份文件经过了 $q$ 次加密,每次加密是交换两个长宽分别相等的矩形,由于长者有点老花眼,所以他加密的时候两个矩形间任意一对元素曼哈顿距离大于 $1$。
由于好奇,你开始解密这份文件,方便起见,加密操作已经倒序给你,你只要按顺序操作一遍便能解密。当你破解完这个文件,你会发现你的生命少了做这道题的时间。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
// ==============================
// author: memset0
// website: https://memset0.cn
// ==============================
#include <bits/stdc++.h>
#define ll long long

int read() {
int x = 0; bool m = 0; char c = getchar();
while (!isdigit(c) && c != '-') c = getchar();
if (c == '-') m = 1, c = getchar();
while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
if (m) return -x; else return x;
}

const int maxn = 1010, maxm = 1000010;

int n, m, q, ax, ay, bx, by, l, c, lst, tmp;
int al[maxn][maxn], ar[maxn][maxn];

char s[10000010];

void reads(int &l, int &r) {
char c = getchar();
while (c == ' ' || c == '\n') c = getchar();
l = ++lst, r = l - 1;
while (c != ' ' && c != '\n') {
s[++r] = c;
c = getchar();
}
lst = r;
}

void prints(int l, int r) {
for (int i = l; i <= r; i++)
putchar(s[i]);
}

struct node {
int x, y;
node () {}
node (int a, int b) { x = a, y = b; }
};
node au, bu, as, bs;
node ex[maxn][maxn], ey[maxn][maxn];

struct pair {
node a, b;
pair () {}
pair (node x, node y) { a = x, b = y; }
};
std::vector < pair > todo_ex, todo_ey;

node lead_to(int x, int y) {
node u = node(0, 0);
while (x--) u = ex[u.x][u.y];
while (y--) u = ey[u.x][u.y];
return u;
}

void print() {
node u(0, 0);
for (int i = 1; i <= n; i++) {
node v = u = ex[u.x][u.y];
for (int j = 1; j <= m; j++) {
v = ey[v.x][v.y];
prints(al[v.x][v.y], ar[v.x][v.y]);
putchar(' ');
}
putchar('\n');
}
}

void swap_ex(node a, node b) {
todo_ex.push_back(pair(a, b));
}

void swap_ey(node a, node b) {
todo_ey.push_back(pair(a, b));
}

int main() {

n = read(), m = read(), q = read();
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
reads(al[i][j], ar[i][j]);
}
for (int i = 0; i <= n; i++)
for (int j = 0; j <= m; j++) {
ex[i][j] = node(i + 1, j);
ey[i][j] = node(i, j + 1);
}

for (int t = 1; t <= q; t++) {
ax = read(), ay = read();
bx = read(), by = read();
l = read(), c = read();
as = lead_to(ax - 1, ay - 1);
bs = lead_to(bx - 1, by - 1);
au = as, bu = bs;
for (int i = 1; i <= l; i++) {
au = ex[au.x][au.y];
bu = ex[bu.x][bu.y];
swap_ey(au, bu);
}
au = as, bu = bs;
for (int i = 1; i <= c; i++) {
au = ey[au.x][au.y];
bu = ey[bu.x][bu.y];
swap_ex(au, bu);
}
au = as, bu = bs;
for (int i = 1; i <= l; i++) {
au = ex[au.x][au.y];
bu = ex[bu.x][bu.y];
}
for (int i = 1; i <= c; i++) {
au = ey[au.x][au.y];
bu = ey[bu.x][bu.y];
swap_ex(au, bu);
}
au = as, bu = bs;
for (int i = 1; i <= c; i++) {
au = ey[au.x][au.y];
bu = ey[bu.x][bu.y];
}
for (int i = 1; i <= l; i++) {
au = ex[au.x][au.y];
bu = ex[bu.x][bu.y];
swap_ey(au, bu);
}
for (std::vector < pair > ::iterator it = todo_ex.begin();
it != todo_ex.end();
it++)
std::swap(ex[it->a.x][it->a.y], ex[it->b.x][it->b.y]);
for (std::vector < pair > ::iterator it = todo_ey.begin();
it != todo_ey.end();
it++)
std::swap(ey[it->a.x][it->a.y], ey[it->b.x][it->b.y]);
todo_ex.clear();
todo_ey.clear();
}
print();

return 0;
}