题解：AT_past202005_i 行列操作

ylch · 2025-02-02 22:51:48 · 题解

Description

我们有一个 n \times n 的矩阵 a，其元素满足以下条件：

接下来，我们需要对这个矩阵进行 q 次操作，操作类型包括：

1. 交换两行的元素。
2. 交换两列的元素。
3. 转置矩阵。
4. 查询某个位置的元素值。

数据范围：n,q \le 10^5

Analysiss

发现每次操作貌似都是针对行和列的，和具体数字无关。所以我们只要用两个数组记录行和列的变化，在处理询问时按照公式 O(1) 处理出值即可。

具体地，可以记录两个数组 row,col，其中 row[i] 表示初始矩阵第 i 行在当前矩阵中的实际存储位置（可以理解为两个指针）。初始状态即为 row[i]=i，表示没有交换。对于 col 的处理同理。

考虑处理操作，操作 1,2 显然，只要交换对应的行、列指针即可。操作 4 可以根据题面给的递推式求值。

现在本题的难点来到了操作 3：矩阵转置。

考虑拿一个矩阵模拟一下，对于以下矩阵：

1 2 3
4 5 6
7 8 9

转置后的矩阵如下：

1 4 7
2 5 8
3 6 9

我们发现，转置矩阵好像就是把第一列与第一行交换，第二列与第二行交换，以此类推。

也就是说，在查询转置矩阵位置 (x,y) 时，实际要查询的是原矩阵位置 (y,x) 的值。再转置一次呢？查询原矩阵的位置又变回 (x,y)。

以上发现带给我们几个思路：

1. 如果矩阵转置了一次，我们只要把存储行、列的数组整体交换一下，就可以实现目标。

   这个有点抽象，可以理解为矩阵转置本身其实不需要交换两个数组，只要询问时交换行列坐标就行。但我们还要处理操作 1,2，这样做能保证在进行若干次操作 1,2 后再进行操作 3 换回来时，换回来的行、列顺序是交换后的正确位置。具体见代码。

2. 矩阵转置只有两种结果来回变，根据奇偶性决定，奇变偶不变。所以我们可以用标记变量记录当前矩阵的答案是否为转置状态，从而处理询问。

3. 在处理询问 (x,y) 时，如果矩阵处于转置状态，则答案应该是位置 (col[y], row[x]) 的值；否则答案应为 (row[x],col[y]) 的值。

Code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void solve()
{
    int n, q;
    cin >> n >> q;

    // 初始化行和列的映射
    vector <int> row(n + 1), col(n + 1);
    for(int i = 1; i <= n; i ++){
        row[i] = col[i] = i;
    }

    bool flag = false; // 矩阵转置的标记
    while(q --){
        int op; cin >> op;
        if(op == 1){
            int x, y; cin >> x >> y;
            swap(row[x], row[y]);
        }
        else if(op == 2){
            int x, y; cin >> x >> y;
            swap(col[x], col[y]);
        }
        else if(op == 3){
            flag ^= 1;
            swap(row, col);
        }
        else if(op == 4){
            int x, y; cin >> x >> y;
            int i = row[x], j = col[y];
            if(flag) swap(i, j);
            cout << 1LL * n * (i - 1) + (j - 1) << '\n'; // long long！！！
        }
    }
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

时间复杂度：每次操作的时间复杂度为 O(1)，总时间复杂度为 O(n+q)。

End

管理员大大辛苦啦~

这里是 ylch，谢谢大家！