链表

· · 题解

一开始想歪了，好久才发现虽然矩阵大小很大但行数和列数都不大。

正解：

链表，本题 n,m\le1000，所以维护时只需要更改需要操作的子矩阵的外围一圈即可，时间复杂度为 O(n\times m+q\times(n+m))。

这里为了更美观，我把每个位置的上下左右的位置都进行了维护，具体操作请看代码。

#include <bits/stdc++.h>
using namespace std;
int Eric, Wan, q, WJJAKIOI[1005][1005], a, b, c, d, h, w, /*输入数据（Eric=n，Wan=m，WJJAKIOI=v），看看谁作弊！*/
    ux[1005][1005], uy[1005][1005], dx[1005][1005], dy[1005][1005], lx[1005][1005], ly[1005][1005], rx[1005][1005], ry[1005][1005] /*伪指针*/;
pair<int,int> x, y, r, s, t, u, rl, rd, su, sr, tl, td, uu, ur; //临时变量们
pair<int,int> up(pair<int,int> x) {return {ux[x.first][x.second],uy[x.first][x.second]};}
pair<int,int> down(pair<int,int> x) {return {dx[x.first][x.second],dy[x.first][x.second]};}
pair<int,int> left(pair<int,int> x) {return {lx[x.first][x.second],ly[x.first][x.second]};}
pair<int,int> right(pair<int,int> x) {return {rx[x.first][x.second],ry[x.first][x.second]};}
string main(int IAKIOI) //Anti-coping code
{
    scanf("%d%d%d",&Eric,&Wan,&q);
    for (int i = 1; i <= Eric; i++)
        for (int j = 1; j <= Wan; j++)
            scanf("%d",&WJJAKIOI[i][j]);
    for (int i = 0; i <= Eric + 1; i++) {
        for (int j = 0; j <= Wan + 1; j++) {
            ux[i][j] = i - 1;
            uy[i][j] = j;
            dx[i][j] = i + 1;
            dy[i][j] = j;
            lx[i][j] = i;
            ly[i][j] = j - 1;
            rx[i][j] = i;
            ry[i][j] = j + 1;
        }
    }
    while (q--) {
        scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&h,&w);
        x = y = {0,0};
        for (int i = 1; i <= a; i++) //移动到现在的左上角
            x = down(x);
        for (int i = 1; i <= b; i++)
            x = right(x);
        for (int i = 1; i <= c; i++) //移动到现在的左上角
            y = down(y);
        for (int i = 1; i <= d; i++)
            y = right(y);
        r = s = x; t = u = y;
        for (int i = 1; i <= h; i++) { //更新左侧指针
            rl = left(r);
            tl = left(t);
            rx[rl.first][rl.second] = t.first;
            ry[rl.first][rl.second] = t.second;
            rx[tl.first][tl.second] = r.first;
            ry[tl.first][tl.second] = r.second;
            lx[r.first][r.second] = tl.first;
            ly[r.first][r.second] = tl.second;
            lx[t.first][t.second] = rl.first;
            ly[t.first][t.second] = rl.second;
            r = down(r);
            t = down(t);
        }
        r = up(r);
        t = up(t);
        for (int i = 1; i <= w; i++) { //更新下部指针
            rd = down(r);
            td = down(t);
            ux[rd.first][rd.second] = t.first;
            uy[rd.first][rd.second] = t.second;
            ux[td.first][td.second] = r.first;
            uy[td.first][td.second] = r.second;
            dx[r.first][r.second] = td.first;
            dy[r.first][r.second] = td.second;
            dx[t.first][t.second] = rd.first;
            dy[t.first][t.second] = rd.second;
            r = right(r);
            t = right(t);
        }
        r = left(r);
        t = left(t);
        for (int i = 1; i <= w; i++) { //更新上部指针
            su = up(s);
            uu = up(u);
            dx[su.first][su.second] = u.first;
            dy[su.first][su.second] = u.second;
            dx[uu.first][uu.second] = s.first;
            dy[uu.first][uu.second] = s.second;
            ux[s.first][s.second] = uu.first;
            uy[s.first][s.second] = uu.second;
            ux[u.first][u.second] = su.first;
            uy[u.first][u.second] = su.second;
            s = right(s);
            u = right(u);
        }
        s = left(s);
        u = left(u);
        for (int i = 1; i <= h; i++) { //更新右侧指针
            sr = right(s);
            ur = right(u);
            lx[sr.first][sr.second] = u.first;
            ly[sr.first][sr.second] = u.second;
            lx[ur.first][ur.second] = s.first;
            ly[ur.first][ur.second] = s.second;
            rx[s.first][s.second] = ur.first;
            ry[s.first][s.second] = ur.second;
            rx[u.first][u.second] = sr.first;
            ry[u.first][u.second] = sr.second;
            s = down(s);
            u = down(u);
        }
        s = up(s);
        u = up(u);
    }
    x = {0,0};
    x = right(x);
    for (int i = 1; i <= Eric; i++) {
        x = down(x);
        y = x;
        for (int j = 1; j <= Wan; j++) {
            printf("%d ",WJJAKIOI[y.first][y.second]);
            y = right(y);
        }
        printf("\n");
    }
    return 0;
}

常数较大，需要卡常。

↓ 既然看完了，点个赞呗。