题解 CF706E 【Working routine】

小周猪猪 · 2019-10-01 20:59:55 · 题解

\mathrm{Solution}

一道非常神奇的题，这道题的解题关键就在于如何解决又换矩阵这一个问题。

一些废话：观察数据范围，我们发现可以用O((n+m)q)的复杂度解决问题。

考虑链的做法：怎么做矩阵的交换最方便呢，由于矩阵不想交，我们可以维护一个链表，即对[l_1,r_1]和[l_2,r_2]进行交换的话，需要将r_1和r_2的后继交换。

那么维护到矩阵上同理，我们可以维护一个十字链表，对于每一个节点记录右边的点和下面的节点，这样我们就可以可以做到快速交换了。

那么如何交换呢，这里我们需要在O(n+m)的时间内完成交换。

• 首先找到(x_1,y_1)的编号，再找到(x_2,y_2)的编号。
• 先向右w时，交换下指针；再向下h时，交换右指针。
• 先向下h时，交换右指针；再向右w时，交换下指针。

最后是输出，这个就很简单了，直接遍历链表即可。

\mathrm{Code}

#include <bits/stdc++.h>

using namespace std;
const int N = 1200;

int n, m, k;
struct List {
    int val, r, d;
} a[N * N];

int read(void)
{
    int s = 0, w = 0; char c = getchar();
    while (c < '0' || c > '9') w |= c == '-', c = getchar();
    while (c >= '0' && c <= '9') s = s*10+c-48, c = getchar();
    return w ? -s : s;
}

inline int C(int x,int y) {
    return x * (m + 1) + y;
}

void change(void)
{
    int x1 = read(), y1 = read(), x2 = read(), y2 = read();
    int h = read(), w = read(), t1 = 0, t2 = 0;
    for (int i=1;i<x1;++i) t1 = a[t1].d;
    for (int i=1;i<y1;++i) t1 = a[t1].r;
    for (int i=1;i<x2;++i) t2 = a[t2].d;
    for (int i=1;i<y2;++i) t2 = a[t2].r;
    int p1 = t1, p2 = t2;
    for (int i=1;i<=w;++i) {
        p1 = a[p1].r, p2 = a[p2].r;
        swap(a[p1].d,a[p2].d);
    }
    for (int i=1;i<=h;++i) {
        p1 = a[p1].d, p2 = a[p2].d;
        swap(a[p1].r,a[p2].r);
    }
    p1 = t1, p2 = t2;
    for (int i=1;i<=h;++i) {
        p1 = a[p1].d, p2 = a[p2].d;
        swap(a[p1].r,a[p2].r);
    }
    for (int i=1;i<=w;++i) {
        p1 = a[p1].r, p2 = a[p2].r;
        swap(a[p1].d,a[p2].d);
    }
    return;
}

void output(void)
{
    int t = 0;
    for (int i=1;i<=n;++i)
    {
        t = a[t].d;
        int p = t;
        for (int i=1;i<=m;++i) {
            p = a[p].r;
            printf("%d ", a[p].val);
        }
        puts("");
    }
    return;
}

int main(void)
{
    n = read(), m = read(), k = read();
    for (int i=1;i<=n;++i)
        for (int j=1;j<=m;++j)
            a[C(i,j)].val = read();
    for (int i=0;i<=n;++i)
        for (int j=0;j<=m;++j) {
            a[C(i,j)].r = C(i,j+1);
            a[C(i,j)].d = C(i+1,j);
        }
    while (k --) change();
    output();
    return 0;
}