4289. [THUPC 2025 Final] 列队

【题目背景】

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

【题目描述】

定义 $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}$ 的值。

【输出格式】

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

【输入样例】

2 2 10
1 4
2 3
2 1 2
1 1 1 1 2
2 1 2
1 1 1 1 2
1 1 2 2 1
2 2 1
2 2 2
1 1 1 2 2
2 1 1
2 2 1

【输出样例】

4
3
3
4
1
2

【提示】

第一次查询的时候矩阵形如

1 4
2 3

我们发现第一次按行排列时就没能使得矩阵改变，因此答案就是第一行第二列的元素，也就是 $4$。

第二次查询的时候矩阵形如

4 1
2 3

我们先按行排序，变成

1 4
2 3

再按列排序，变成

1 3
2 4

再尝试按行排序，发现不能成功排序。因此答案就是此时第一行第二列的元素，也就是 $3$。

【来源】

清华大学学生算法协会 GitLink 仓库