语言月赛 202406 数组交换

题目概述

• 有一个 $n \times m$ 的二维数组 $a$。
• 有三种操作：
  • 交换两行
  • 交换两列
  • 查询某个元素的值
• 操作执行 $q$ 次后，需要输出所有查询操作的结果和最终数组状态。

---

关键点与难点

• 直接交换行列数组会导致 $O(nm)$ 的代价，执行 $q$ 次操作会非常慢。
• 题目规模最大 $n, m \leq 1000$，$q \leq 10^5$，逐个元素交换不可行。

---

核心思路：用映射数组模拟行列交换

1. 维护两个数组：

   • r：长度为 $n$，r[i] 表示当前第 $i$ 行实际对应的是原始数据中的哪一行。
   • c：长度为 $m$，c[j] 表示当前第 $j$ 列实际对应的是原始数据中的哪一列。

2. 初始化：

   • r[i] = i （表示初始时第 $i$ 行映射到自身）
   • c[j] = j

3. 交换行操作（类型1）：

   • 交换 r[x] 和 r[y] 的值

4. 交换列操作（类型2）：

   • 交换 c[x] 和 c[y]

5. 查询操作（类型3）：

   • 查询 $a[r[x], c[y]]$ 即为当前 $a_{x,y}$ 的值。

6. 输出最终数组：

   • 对所有 $i \in [1, n]$, $j \in [1, m]$ 输出 $a[r[i], c[j]]$

---

示例代码

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1e3 + 5;
int n, m, q, r[N], c[N];
char a[N][N];
int main() 
{
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++)
    {
        r[i] = i;
        for (int j = 1; j <= m; j++)
        {
            c[j] = j;
            cin >> a[i][j];
        }
    }
    while (q--)
    {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) swap(r[x], r[y]);
        if (op == 2) swap(c[x], c[y]);
        if (op == 3) cout << a[r[x]][c[y]] << "\n";
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
            cout << a[r[i]][c[j]];
        cout << "\n";
    }
    return 0;
}

优势分析

• 所有行列交换操作都是 $O(1)$ 时间复杂度，只修改映射数组。
• 查询操作也是 $O(1)$，直接用映射数组定位。
• 最后输出数组时，按映射访问即可，无需多次交换。

---

复杂度

时间复杂度：$O(nm + q)$，其中 $nm$ 用于输入和输出，$q$ 用于操作处理。

空间复杂度：$O(nm)$ 用于存储数组，$O(n + m)$ 用于映射数组。