题解 CF706E 【Working routine】

优雅的指针

题意

给出矩阵上各点的权值，并给出 $q$ 次左上角坐标 $x_1, y_1$ 、 $x_2, y_2$ 即长宽 $h, w$，交换这两个矩阵，求最后矩阵的上各点的值。

tips

一开始看到交换一段矩阵，笔者不免想到用 fhq Treap 来维护每一段并交换，可惜复杂度堪忧， “ 猝死 ” 于 #11。有兴趣的小伙伴可以来看一下 $??>$ here。

其实正解是用指针描述每一个点的信息。我维护的是每个点的上（up）下 ( down ) 左 ( l ) 右 ( r )。

先在原先 $n * m$ 的矩阵周围绕上一圈作为边界 $-->$

	for(int i = 0; i <= n + 1 ; i++)//这两个是边界上点与矩阵内点的关系a[i][0].r = calc(i, 1), a[i][n + 1].l = calc(i, n);for(int i = 0; i <= m + 1; i++)a[0][i].down = calc(1, i), a[n + 1][i].up = calc(n, i);for(int i = 0; i <= m; i++)//这些是边界上各点之间的关系a[0][i].r = calc(0, i + 1), a[n + 1][i].r = calc(n + 1, i + 1);for(int i = 1; i <= m + 1; i++)a[0][i].l = calc(0, i - 1), a[n + 1][i].l = calc(n + 1, i - 1);for(int i = 0; i <= n; i++)a[i][0].down = calc(i + 1, 0), a[i][n + 1].down = calc(i + 1, n + 1);for(int i = 1; i <= n + 1; i++)a[i][0].up = calc(i - 1, 0), a[i][n + 1].up = calc(i - 1, n + 1);

然后是矩阵内各点的关系 $-->$

	for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){a[i][j].l = calc(i, j - 1);a[i][j].r = calc(i, j + 1);a[i][j].up = calc(i - 1, j);a[i][j].down = calc(i + 1, j);}}

接下来是关键：我们交换的矩阵的内部关系是不变的，而只有最外围会改变对应关系，我们可以做一个简单的模拟 $-->$

初始每个点的上下左右如图所示，周围的 0 是边界，如果把左上角 $3 * 3$ 矩阵和右下角 $3 * 3$ 矩阵交换，中间的相对位置是不会改变的，如（2， 2）的 1，上还是 1，下还是 4 , 左还是 4，右还是 1。所以我们只需要维护周围一圈的信息好了。但是该如何找到矩阵修改后的左上角端点呢？我们可以从 （0， 0）出发，dfs找到，并逐步 dfs（根据其 r 和 down ） 下去，找到端点，在对调信息即可。我是先一步枚举竖直方向，考虑到可能会改变左右端点，故在枚举水平方向时在 dfs2 中先 dfs 水平方向（其实也没必要，无论水平是否交换矩阵上下交换结果不变 ）。

这是 dfs （dfs2 同理） $-->$

inline pair<int, int> dfs(int x, int y, int xx, int yy){//xx，yy 为将要走的步数，x、y 为当前坐标。用 pair 传递目标的坐标if(xx){pair <int, int> now = re_calc(a[x][y].down );return dfs(now.first , now.second , xx - 1, yy);}if(yy){pair <int, int > now = re_calc(a[x][y].r );return dfs(now.first , now.second , xx, yy - 1);}return make_pair(x, y);
}
}

由于笔者能力有限，在维护信息时打的又臭又长，但个人感觉还是比较对称美观的 （逃

下面给出矩阵左端的维护代码 $-->$

	pair <int, int> now1 = dfs(0, 0, x1 - 1, y1);pair <int, int> now2 = dfs(0, 0, x2 - 1, y2);for(int j = 0; j < h; j++){now1 = dfs(now1.first , now1.second , 1, 0);now2 = dfs(now2.first , now2.second , 1, 0);pair <int, int> u = re_calc(a[now1.first][now1.second ].l );pair <int, int> v = re_calc(a[now2.first][now2.second ].l );a[u.first ][u.second ].r = calc(now2.first, now2.second );a[v.first ][v.second ].r = calc(now1.first, now1.second );a[now1.first][now1.second ].l = calc(v.first , v.second );a[now2.first][now2.second ].l = calc(u.first , u.second );}

最后 dfs 并输出即可。

下面给出总代码 $-->$

#include <cstdio>
#include <cctype>
#include <algorithm>
#define ll long long
#define inf 0x3f3f3f3fusing namespace std;inline int read(){int x=0,w=0;char ch=getchar();while (!isdigit(ch))w|=ch=='-',ch=getchar();while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();return w?-x:x;
}struct node{int l, r, up, down;int val;
}a[1005][1005];int n, m, q, b[1005][1005], cnt; inline int calc(int x, int y){return x * (m + 3) + y;
}inline pair<int, int> re_calc(int p){return make_pair(p / (m + 3), p % (m + 3));
}inline pair<int, int> dfs(int x, int y, int xx, int yy){if(xx){pair <int, int> now = re_calc(a[x][y].down );return dfs(now.first , now.second , xx - 1, yy);}if(yy){pair <int, int > now = re_calc(a[x][y].r );return dfs(now.first , now.second , xx, yy - 1);}return make_pair(x, y);
}inline pair<int, int> dfs2(int x, int y, int xx, int yy){if(yy){pair <int, int> now = re_calc(a[x][y].r );return dfs2(now.first , now.second , xx, yy - 1);}if(xx){pair <int, int > now = re_calc(a[x][y].down );return dfs2(now.first , now.second , xx - 1, yy);}return make_pair(x, y);
}int main(){n = read();m = read();q = read();for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){a[i][j].val = read();}}for(int i = 0; i <= n + 1 ; i++)a[i][0].r = calc(i, 1), a[i][n + 1].l = calc(i, n);for(int i = 0; i <= m + 1; i++)a[0][i].down = calc(1, i), a[n + 1][i].up = calc(n, i);for(int i = 0; i <= m; i++)a[0][i].r = calc(0, i + 1), a[n + 1][i].r = calc(n + 1, i + 1);for(int i = 1; i <= m + 1; i++)a[0][i].l = calc(0, i - 1), a[n + 1][i].l = calc(n + 1, i - 1);for(int i = 0; i <= n; i++)a[i][0].down = calc(i + 1, 0), a[i][n + 1].down = calc(i + 1, n + 1);for(int i = 1; i <= n + 1; i++)a[i][0].up = calc(i - 1, 0), a[i][n + 1].up = calc(i - 1, n + 1);for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){a[i][j].l = calc(i, j - 1);a[i][j].r = calc(i, j + 1);a[i][j].up = calc(i - 1, j);a[i][j].down = calc(i + 1, j);}}for(int i = 1; i <= q; i++){int x1 = read(), y1 = read(), x2 = read(), y2 = read(), h = read(), w = read();pair <int, int> now1 = dfs(0, 0, x1 - 1, y1);pair <int, int> now2 = dfs(0, 0, x2 - 1, y2);pair <int, int> now3 = dfs(0, 0, x1 - 1, y1 + w - 1);pair <int, int> now4 = dfs(0, 0, x2 - 1, y2 + w - 1);for(int j = 0; j < h; j++){now1 = dfs(now1.first , now1.second , 1, 0);now2 = dfs(now2.first , now2.second , 1, 0);now3 = dfs(now3.first , now3.second , 1, 0);now4 = dfs(now4.first , now4.second , 1, 0);pair <int, int> u = re_calc(a[now1.first][now1.second ].l );pair <int, int> v = re_calc(a[now2.first][now2.second ].l );a[u.first ][u.second ].r = calc(now2.first, now2.second );a[v.first ][v.second ].r = calc(now1.first, now1.second );a[now1.first][now1.second ].l = calc(v.first , v.second );a[now2.first][now2.second ].l = calc(u.first , u.second );u = re_calc(a[now3.first][now3.second ].r );v = re_calc(a[now4.first][now4.second ].r );a[u.first ][u.second ].l = calc(now4.first, now4.second);a[v.first ][v.second ].l = calc(now3.first, now3.second);a[now3.first][now3.second].r = calc(v.first , v.second );a[now4.first][now4.second].r = calc(u.first , u.second );}now1 = dfs2(0, 0, x1, y1 - 1);now2 = dfs2(0, 0, x2, y2 - 1);now3 = dfs2(0, 0, x1 + h - 1, y1 - 1);now4 = dfs2(0, 0, x2 + h - 1, y2 - 1);for(int j = 0; j < w; j++){now1 = dfs(now1.first , now1.second , 0, 1);now2 = dfs(now2.first , now2.second , 0, 1);now3 = dfs(now3.first , now3.second , 0, 1);now4 = dfs(now4.first , now4.second , 0, 1);pair <int, int> u = re_calc(a[now1.first ][now1.second ].up );pair <int, int> v = re_calc(a[now2.first ][now2.second ].up );a[u.first ][u.second ].down = calc(now2.first , now2.second );a[v.first ][v.second ].down = calc(now1.first , now1.second );a[now1.first ][now1.second ].up = calc(v.first , v.second );a[now2.first ][now2.second ].up = calc(u.first , u.second );u = re_calc(a[now3.first ][now3.second ].down );v = re_calc(a[now4.first ][now4.second ].down );a[u.first ][u.second ].up = calc(now4.first , now4.second );a[v.first ][v.second ].up = calc(now3.first , now3.second );a[now3.first ][now3.second ].down = calc(v.first , v.second );a[now4.first ][now4.second ].down = calc(u.first , u.second );}}for(int i = 1; i <= n; i++){pair <int, int> now = dfs(0, 0, i, 0);for(int j = 1; j <= m; j++){now = dfs(now.first , now.second , 0, 1);printf("%d ",a[now.first ][now.second ].val );}printf("\n");}return 0;
}

完结撒花??ヽ(°▽°)ノ?