cf#367E-Working routine 十字链表

http://codeforces.com/contest/706/problem/E

题意：给你一个矩阵，要你进行q次操作，输出最后的矩阵

操作：选择两个子矩阵交换，保证两个子矩阵没有边的接触。

数据范围

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.

看这个数据范围。。。。似乎可以强行用splay交换怼过去？？？据说会T。。。

官解是十字链表搞，如果建立好十字链表后

每次交换矩阵，其实变化的之后该子矩阵的周围一圈的指针。那么我们只需要暴力修改这一圈指针即可，复杂度O（n+m）

并且可以发现，只需要维护一个right和down指针即可。

如果加多一个up,left指针也没问题，如果是只用r和d的话，需要给原矩阵周围覆盖多一圈，以免越界

并且题目说了子矩阵是不会挨在一起的，那么就更不容易越界啦，

（当然即使挨在一起也是可以做得，例如，A矩阵的最后一列与B矩阵的第一列挨着，那么暴力交换掉两个矩阵的最后一列，剩下的矩阵再按正常方法交换即可，复杂度不变）

amazing

#include <cstdio> #include <cmath> #include <cstring> #include <string> #include <algorithm> #include <queue> #include <map> #include <set> #include <vector> #include <iostream> using namespace std; const double pi=acos(-1.0); double eps=0.000001; typedef long long ll; struct node { int v; node *r,*d; }; node aa[1005][1005]; int main() { int n,m,q; cin>>n>>m>>q; for (int i=0; i<=n; i++) aa[i][0].r=&aa[i][1]; for (int i=0; i<=m; i++) aa[0][i].d=&aa[1][i]; for (int i=1; i<=m; i++) aa[0][i].r=&aa[0][i+1]; for (int i=1; i<=n; i++) aa[i][0].d=&aa[i+1][0]; for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) { scanf("%d",&aa[i][j].v); aa[i][j].r=&aa[i][j+1]; aa[i][j].d=&aa[i+1][j]; } int a,b,c,d,h,w; while(q--) { scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&h,&w); node *p1,*p2,*p3,*p4; p3=&aa[a-1][0]; p4=&aa[c-1][0]; for (int i=1; i<b; i++) p3=p3->r; for (int i=1; i<d; i++) p4=p4->r; p1=p3->r,p2=p4->r; for (int i=1; i<=w; i++) { swap(p1->d,p2->d); if (i<w) { p1=p1->r; p2=p2->r; } } p1=p1->d,p2=p2->d; for (int i=1; i<=h; i++) { swap(p1->r,p2->r); p1=p1->d; p2=p2->d; } p1=p3->d,p2=p4->d; for (int i=1; i<=h; i++) { swap(p1->r,p2->r); if (i<h) { p1=p1->d; p2=p2->d; } } p1=p1->r,p2=p2->r; for (int i=1; i<=w; i++) { swap(p1->d,p2->d); p1=p1->r; p2=p2->r; } } node *p; for (int i=1; i<=n; i++) { p=aa[i][0].r; for (int j=1; j<=m; j++) { printf("%d ",p->v); p=p->r; } printf("\n"); } printf("\n"); return 0; }