P12062 [THUPC 2025 决赛] 列队

……所以这个题意和标题是什么关系？

定义 $f(A)$ 为 矩阵 $A$ 经过如下操作后得到的结果： 1. 独立地对矩阵 $A$ 的每行进行排序，使得各行中的元素从左到右单调不降。如果排序过后的矩阵和排序之前完全相同，则此次变换停止，否则再进行 2. 中描述的操作。 2. 独立地对矩阵 $A$ 的每列进行排序，使得各列中的元素从上到下单调不降。如果排序过后的矩阵和排序之前完全相同，则此次变换停止，否则再进行 1. 中描述的操作。 现给定一个 $n$ 行 $m$ 列的整数矩阵 $P$，满足$1\le P_{ij}\le n\times m$ 且矩阵中元素互不相同。 接下来有 $q$ 次操作，操作有以下两种： - 修改操作：给定矩阵中的两个位置 $(x_1,y_1)$ 和 $(x_2,y_2)$，将这两个位置上的元素交换，即交换 $P_{x_1y_1}$ 和 $P_{x_2y_2}$。 - 查询操作：给定矩阵中的一个位置 $(x,y)$，输出矩阵 $f(P)$ 中该位置的元素，即$f(P)_{xy}$。注意，**查询操作并不会真的改变矩阵形态**。

第一行依次输入三个整数 $n,m,q\ (1\le n\times m\le2\times10^5,1\le q\le2\times10^5)$。 接下来 $n$ 行，每行 $m$ 个整数，依次描述矩阵 $P$ 各行各列的元素。保证这些元素均在 $1\sim n\times m$ 之间且互不相同。 接下来 $q$ 行，每行先是一个整数 $\text{opt}\in\{1,2\}$，表示操作种类。 - $\text{opt}=1$ 代表一个修改操作。接下来读入四个整数 $x_1,y_1,x_2,y_2\ (1\le x_1,x_2\le n,1\le y_1,y_2\le m)$，表示交换 $P_{x_1y_1}$ 和 $P_{x_2y_2}$。 - $\text{opt}=2$ 代表一个查询操作。接下来读入两个整数 $x,y\ (1\le x\le n,1\le y\le m)$，表示查询 $f(P)_{xy}$ 的值。

对每组查询操作，输出对应元素的值。

### 样例 #1 解释 第一次查询的时候矩阵形如 ```plain 1 4 2 3 ``` 我们发现第一次按行排列时就没能使得矩阵改变，因此答案就是第一行第二列的元素，也就是 $4$。 第二次查询的时候矩阵形如 ```plain 4 1 2 3 ``` 我们先按行排序，变成 ```plain 1 4 2 3 ``` 再按列排序，变成 ```plain 1 3 2 4 ``` 再尝试按行排序，发现不能成功排序。因此答案就是此时第一行第二列的元素，也就是 $3$。 ### 来源与致谢 来自 THUPC2025（2025 年清华大学学生程序设计竞赛暨高校邀请赛）决赛。感谢 THUSAA 的提供的题目。 数据、题面、标程、题解等请参阅 THUPC 官方仓库 。