#B1333. 数组交换

数组交换

【题目描述】

给定一个 nn 行 mm 列的矩阵。

最开始,第 ii 行第 jj 列的元素为 i×ji\times j。

共有 qq 次操作,每次操作属于以下三种之一:

  • 1 x y:交换第 xx 行和第 yy 行;
  • 2 x y:交换第 xx 列和第 yy 列;
  • 3 x y:询问当前第 xx 行第 yy 列的元素值。

对于每次询问,请输出对应的元素值。


【输入描述】

第一行包含三个正整数 n,m,qn,m,q,分别表示矩阵的行数、列数和操作次数。

接下来 qq 行,每行包含三个整数 op,x,yop,x,y,表示一次操作。

其中:

  • 当 op=1op=1 时,表示交换第 xx 行和第 yy 行;
  • 当 op=2op=2 时,表示交换第 xx 列和第 yy 列;
  • 当 op=3op=3 时,表示询问当前第 xx 行第 yy 列的元素值。

保证:

  • 1≤n,m,q≤1051\le n,m,q\le 10^5;
  • 对于操作 1 x y,有 1≤x,y≤n1\le x,y\le n;
  • 对于操作 2 x y,有 1≤x,y≤m1\le x,y\le m;
  • 对于操作 3 x y,有 1≤x≤n, 1≤y≤m1\le x\le n,\ 1\le y\le m。

【输出描述】

对于每次 3 x y 操作,输出一行一个整数,表示当前第 xx 行第 yy 列的元素值。


【样例 1】

【样例 1 输入】

2 3 5
3 1 3
1 1 2
3 1 3
2 2 3
3 2 2

【样例 1 输出】

3
6
3

【样例 1 解释】

初始矩阵为:

1 2 3
2 4 6

第一次询问的是第 11 行第 33 列,答案为 1×3=31\times 3=3。

交换第 11 行和第 22 行后,第二次询问的是当前第 11 行第 33 列,答案为 2×3=62\times 3=6。

交换第 22 列和第 33 列后,第三次询问的是当前第 22 行第 22 列,答案为 1×3=31\times 3=3。


【样例 2】

【样例 2 输入】

3 4 8
3 2 4
1 1 3
3 1 4
2 2 4
3 3 2
1 2 3
2 1 3
3 1 1

【样例 2 输出】

8
12
4
9

【数据规模与约定】

测试点编号 分数 特殊性质
1 ~ 8 80 1≤n,m,q≤20001\le n,m,q\le 2000
9 ~ 10 20 1≤n,m,q≤1051\le n,m,q\le 10^5