题解 CF706E 【Working routine】

HECZ · 2020-08-10 18:03:52 · 题解

简述题意：

给定一个 1000 \times 1000 的矩阵，每次交换任意两个不重合的子矩阵，求最后的结果

思路1（部分分）：

平衡树。复杂度 O(m \times n \log n)，但是很遗憾，由于常数实在过大，导致最后得分甚至可能不如暴力 memcpy。

思路2（正解）：

链表。大致思路是维护一个矩形的链表，每次交换分别把两块矩阵取出再拼接上去。

#include <bits/stdc++.h>
#typedef long long ll;

int read() {
    int x = 0; bool m = 0; char c = getchar();
    while (!isdigit(c) && c != '-') c = getchar();
    if (c == '-') m = 1, c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    if (m) return -x; else return x;
}

const int maxn = 1010, maxm = 1000010;

int n, m, q, ax, ay, bx, by, l, c, lst, tmp;
int al[maxn][maxn], ar[maxn][maxn];

char s[10000010];

void reads(int &l, int &r) {
    char c = getchar();
    while (c == ' ' || c == '\n') c = getchar();
    l = ++lst, r = l - 1;
    while (c != ' ' && c != '\n') {
        s[++r] = c;
        c = getchar();
    }
    lst = r;
}

void prints(int l, int r) {
    for (int i = l; i <= r; i++)
        putchar(s[i]);
}

struct node {
    int x, y;
    node () {}
    node (int a, int b) { x = a, y = b; }
};
node au, bu, as, bs;
node ex[maxn][maxn], ey[maxn][maxn];

struct pair {
    node a, b;
    pair () {}
    pair (node x, node y) { a = x, b = y; }
};
std::vector < pair > todo_ex, todo_ey;

node lead_to(int x, int y) {
    node u = node(0, 0);
    while (x--) u = ex[u.x][u.y];
    while (y--) u = ey[u.x][u.y];
    return u;
}

void print() {
    node u(0, 0);
    for (int i = 1; i <= n; i++) {
        node v = u = ex[u.x][u.y];
        for (int j = 1; j <= m; j++) {
            v = ey[v.x][v.y];
            prints(al[v.x][v.y], ar[v.x][v.y]);
            putchar(' ');
        }
        putchar('\n');
    }
}

void swap_ex(node a, node b) {
    todo_ex.push_back(pair(a, b));
}

void swap_ey(node a, node b) {
    todo_ey.push_back(pair(a, b));
}

int main() {

    n = read(), m = read(), q = read();
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            reads(al[i][j], ar[i][j]);
        }
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= m; j++) {
            ex[i][j] = node(i + 1, j);
            ey[i][j] = node(i, j + 1);
        }

    for (int t = 1; t <= q; t++) {
        ax = read(), ay = read();
        bx = read(), by = read();
        l = read(), c = read();
        as = lead_to(ax - 1, ay - 1);
        bs = lead_to(bx - 1, by - 1);
        au = as, bu = bs;
        for (int i = 1; i <= l; i++) {
            au = ex[au.x][au.y];
            bu = ex[bu.x][bu.y];
            swap_ey(au, bu);
        }
        au = as, bu = bs;
        for (int i = 1; i <= c; i++) {
            au = ey[au.x][au.y];
            bu = ey[bu.x][bu.y];
            swap_ex(au, bu);
        }
        au = as, bu = bs;
        for (int i = 1; i <= l; i++) {
            au = ex[au.x][au.y];
            bu = ex[bu.x][bu.y];
        }
        for (int i = 1; i <= c; i++) {
            au = ey[au.x][au.y];
            bu = ey[bu.x][bu.y];
            swap_ex(au, bu);
        }
        au = as, bu = bs;
        for (int i = 1; i <= c; i++) {
            au = ey[au.x][au.y];
            bu = ey[bu.x][bu.y];
        }
        for (int i = 1; i <= l; i++) {
            au = ex[au.x][au.y];
            bu = ex[bu.x][bu.y];
            swap_ey(au, bu);
        }
        for (std::vector < pair > ::iterator it = todo_ex.begin();
                it != todo_ex.end();
                it++)
            std::swap(ex[it->a.x][it->a.y], ex[it->b.x][it->b.y]);
        for (std::vector < pair > ::iterator it = todo_ey.begin();
                it != todo_ey.end();
                it++)
            std::swap(ey[it->a.x][it->a.y], ey[it->b.x][it->b.y]);
        todo_ex.clear();
        todo_ey.clear();
    }
    print();

    return 0;
}