E. Working routine time limit per test 2.5 seconds memory limit per test 256 megabytes input standard input output standard output
Vasiliy finally got to work, where there is a huge amount of tasks waiting for him. Vasiliy is given a matrix consisting of n rows and mcolumns and q tasks. Each task is to swap two submatrices of the given matrix.
For each task Vasiliy knows six integers ai, bi, ci, di, hi, wi, where ai is the index of the row where the top-left corner of the first rectangle is located, bi is the index of its column, ci is the index of the row of the top-left corner of the second rectangle, di is the index of its column, hi is the height of the rectangle and wi is its width.
It's guaranteed that two rectangles in one query do not overlap and do not touch, that is, no cell belongs to both rectangles, and no two cells belonging to different rectangles share a side. However, rectangles are allowed to share an angle.
Vasiliy wants to know how the matrix will look like after all tasks are performed.
Input
The first line of the input contains three integers n, m and q (2 ≤ n, m ≤ 1000, 1 ≤ q ≤ 10 000) — the number of rows and columns in matrix, and the number of tasks Vasiliy has to perform.
Then follow n lines containing m integers vi, j (1 ≤ vi, j ≤ 109) each — initial values of the cells of the matrix.
Each of the following q lines contains six integers ai, bi, ci, di, hi, wi (1 ≤ ai, ci, hi ≤ n, 1 ≤ bi, di, wi ≤ m).
Output
Print n lines containing m integers each — the resulting matrix.
Examples input
4 4 2
1 1 2 2
1 1 2 2
3 3 4 4
3 3 4 4
1 1 3 3 2 2
3 1 1 3 2 2
output
4 4 3 3
4 4 3 3
2 2 1 1
2 2 1 1
input
4 2 1
1 1
1 1
2 2
2 2
1 1 4 1 1 2
output
2 2
1 1
2 2
1 1 題意：給你一個n*m的矩陣，然後詢問q次，每次詢問中的 lx，ly，rx，ry，h，w，分别表示兩個子矩陣的左上角坐标和其長寬，要你每次詢問要你交換這兩個子矩陣。經過q次詢問之後，要你輸出最後的矩陣。
題解：（看了CF題解才會寫啊。。。）
當你交換子矩陣時，它子矩陣的結構實際上是不變的。如圖。（橙色是左鄰居，紅色是右鄰居，藍色是上鄰居，綠色是下鄰居）
假如我們想要交換2x2的子矩陣（1,2,5,6）和子矩陣（11,12,15,16）。交換後，我們會發現它們的整體并沒有改變，因為這兩個矩陣仍然有相同的元素。但他們的外邊界變了，因為交換時鄰居變了，是以，我們可以通過修改邊界來達到目的。
先弄個十字連結清單，然後不斷修改鄰居（邊界）。
代碼：
#pragma comment(linker, "/STACK:102400000,102400000")
//#include<bits/stdc++.h>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<map>
#include<cmath>
#include<queue>
#include<set>
#include <utility>
#include<stack>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define mst(a) memset(a, 0, sizeof(a))
#define M_P(x,y) make_pair(x,y)
#define rep(i,j,k) for (int i = j; i <= k; i++)
#define per(i,j,k) for (int i = j; i >= k; i--)
#define lson x << 1, l, mid
#define rson x << 1 | 1, mid + 1, r
const int lowbit(int x) { return x&-x; }
const double eps = 1e-8;
const int INF = 1e9+7;
const ll inf =(1LL<<62) ;
const int MOD = 1e9 + 7;
const ll mod = (1LL<<32);
const int N = 1010;
const int M=2000010;
template <class T1, class T2>inline void getmax(T1 &a, T2 b) {if(b>a)a = b;}
template <class T1, class T2>inline void getmin(T1 &a, T2 b) {if(b<a)a = b;}
int read()
{
int v = 0, f = 1;
char c =getchar();
while( c < 48 || 57 < c ){
if(c=='-') f = -1;
c = getchar();
}
while(48 <= c && c <= 57)
v = v*10+c-48, c = getchar();
return v*f;
}
int a[N][N];
int r[M],d[M];
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
int n,m;
int q,h,w,lx,ly,rx,ry;
n=read();m=read();q=read();
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
{
a[i][j]=read();
}
for(int i=0;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
r[i*(m+1)+j] = i*(m+1)+(j+1);
d[i*(m+1)+j] = (i+1)*(m+1)+j;
}
}
/*
cout<<"-------------------------------------"<<endl;
for(int i=0;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
printf("r[%d]=%d\nd[%d]=%d\n",i,r[i*(m+1)+j],i,d[i*(m+1)+j]);
cout<<"--------"<<endl;
}
}
cout<<"-------------------------------------"<<endl;
*/
while(q--)
{
scanf("%d%d%d%d%d%d",&lx,&ly,&rx,&ry,&h,&w);
int up = 0;
int down = 0;
for(int i=1;i<lx;i++) up=d[up];
for(int i=1;i<ly;i++) up=r[up];
for(int i=1;i<rx;i++) down=d[down];
for(int i=1;i<ry;i++) down=r[down];
int pp=up;
int dd=down;
for(int i=0;i<h;i++){
pp=d[pp];
dd=d[dd];
swap(r[pp],r[dd]);
}
for(int i=0;i<w;i++){
pp=r[pp];
dd=r[dd];
swap(d[pp],d[dd]);
}
pp=up;
dd=down;
for(int i=0;i<w;i++){
pp=r[pp];
dd=r[dd];
swap(d[pp],d[dd]);
}
for(int i=0;i<h;i++){
pp=d[pp];
dd=d[dd];
swap(r[pp],r[dd]);
}
}
int up=0,down;
for(int i=1;i<=n;i++){
up=down=d[up];
for(int j=1;j<=m;j++)
{
down=r[down];
printf("%d ",a[down/(m+1)][down%(m+1)]);
}
puts("");
}
return 0;
}