HDU 5671：Matrix——標記法處理矩陣行列交換與區間加法

題目大意

n×m矩陣（n,m≤1000），q≤100,000次操作：
1 x y：交換第x、y行
2 x y：交換第x、y列
3 x y：第x行每個元素加y
4 x y：第x列每個元素加y
輸出所有操作後的矩陣。

核心技巧：索引映射 + 延遲加法標記

直接模擬交換行/列需O(m)或O(n)，總複雜度O(q·max(n,m))會超時。
觀察：操作只改變行/列的邏輯順序與整體加法偏移，不改變原始數據相對關係。

數據結構設計

• row[i]：當前第i行對應原始矩陣的行號（初始row[i]=i）。
• col[j]：當前第j列對應原始矩陣的列號（初始col[j]=j）。
• addRow[i]：第i行累積加法值（初始0）。
• addCol[j]：第j列累積加法值（初始0）。

操作處理

#include <bits/stdc++.h>
using namespace std;
const int MAX = 1010;
int M[MAX][MAX];
int row[MAX], col[MAX], addRow[MAX], addCol[MAX];

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n, m, q; scanf("%d%d%d", &n, &m, &q);
        for (int i=1; i<=n; ++i) {
            for (int j=1; j<=m; ++j) scanf("%d", &M[i][j]);
            row[i] = i; addRow[i] = 0;
        }
        for (int j=1; j<=m; ++j) { col[j] = j; addCol[j] = 0; }

        while (q--) {
            int op, x, y; scanf("%d%d%d", &op, &x, &y);
            if (op == 1) { swap(row[x], row[y]); swap(addRow[x], addRow[y]); }
            else if (op == 2) { swap(col[x], col[y]); swap(addCol[x], addCol[y]); }
            else if (op == 3) addRow[x] += y;
            else if (op == 4) addCol[x] += y;
        }

        for (int i=1; i<=n; ++i) {
            for (int j=1; j

總結
本題是「標記法/懶惰更新」的教科書級應用。通過維護行列映射與偏移量，將O(q·max(n,m))降為O(q + nm)，體現了「用空間換時間、用間接層解耦操作」的算法設計智慧。