题意理解
定义对矩阵 ( P ) 的操作 ( f(A) )：交替对行、列排序（行内左到右不降，列内上到下不降），直到矩阵不再变化。
给定 ( n \times m ) 矩阵 ( P )，元素互异且为 ( 1 \sim nm ) 的排列。
支持两种操作：

1. 交换两个位置的值。
2. 查询 ( f(P) ) 中某位置的值（不实际改变矩阵）。

关键观察

1. 最终形态唯一性
   经过行列交替排序后，最终矩阵与初始值排列无关，只与元素的多重集有关。
   因为行列排序最终会收敛到“行列均有序”的形态（即每行每列都单调不降）。
   对于排列（元素互异），最终形态是唯一的：将 ( 1 \sim nm ) 按行优先顺序填入矩阵，即 ( f(P)_{i,j} = (i-1)m + j )。

2. 查询转化为定位
   问题转化为：给定当前矩阵 ( P )，经过行列排序后，原位置 ( (x,y) ) 的值会移动到哪？
   设最终矩阵为 ( Q )，其中 ( Q_{i,j} = (i-1)m + j )。
   我们需要找到值 ( Q_{x,y} ) 在当前矩阵 ( P ) 中的位置，但实际要求的是 ( f(P)_{x,y} )，即当前矩阵排序后该位置的值。
   由于最终形态固定，只需知道当前矩阵中第 ( x ) 行第 ( y ) 小的值是多少。

3. 问题转化
   设 ( r_i ) 表示第 ( i ) 行元素按值排序后的序列。
   最终矩阵的第 ( x ) 行由所有行的第 ( x ) 小值组成（因为列排序后每列从上到下递增）。
   因此，( f(P)_{x,y} ) = 所有行中第 ( y ) 小的值按从小到大排序后的第 ( x ) 个值。
   更形式化：

   • 对每行元素排序，设 ( b_{i,j} ) 为第 ( i ) 行第 ( j ) 小的值。
   • 对每列排序后，第 ( j ) 列由上到下为 ( b_{1,j}, b_{2,j}, \dots, b_{n,j} ) 的排序结果。
   • 所以 ( f(P){x,y} ) = 将 ( b{1,y}, b_{2,y}, \dots, b_{n,y} ) 排序后的第 ( x ) 个值。

4. 数据结构维护
   需要支持交换两个位置的值，这会影响两行各自的有序序列。
   我们需要维护每行的有序序列（即每行的值集合），以及各列对应的值集合（即所有行的第 ( y ) 小值集合）。
   由于 ( nm \leq 2 \times 10^5 )，可以分块维护。

5. 分块设计
   将值域 ( [1, nm] ) 分块，每块大小 ( B \approx \sqrt{nm} )。
   维护两个数组：

   • ( c[id][x] )：前 ( id ) 块中，值位于第 ( x ) 行的个数。
   • ( v[id][y] )：前 ( id ) 块中，值在所在行的次序（第几小）恰好为 ( y ) 的个数。
     通过前缀和可以快速查询：对于给定列 ( y )，需要找到第 ( x ) 个值，即找到最小的值 ( val ) 使得前 ( val ) 个值中，有至少 ( x ) 个值的行次序为 ( y )。
     这可以通过在分块上二分实现。

6. 修改操作
   交换两个值 ( a ) 和 ( b )（设 ( a < b )）：

   • 更新它们所在行的有序序列（即更新行内次序）。
   • 更新分块数组 ( c ) 和 ( v )。
   • 若两值在同一行相邻列，还需特殊处理相邻逆序对的计数 ( C )（用于判断矩阵是否已有序）。

7. 查询操作
   若矩阵已有序（( C = 0 )），直接输出原值。
   否则，在分块上扫描，利用 ( v ) 数组累计行次序为 ( y ) 的个数，直到达到 ( x )，输出对应值。

复杂度分析

• 分块大小 ( B )，块数 ( O(\sqrt{nm}) )。
• 修改：更新两个值所在块的前缀和，复杂度 ( O(\sqrt{nm}) )。
• 查询：扫描分块，复杂度 ( O(\sqrt{nm}) )。
• 总复杂度 ( O(q\sqrt{nm}) )，可过 ( q, nm \leq 2 \times 10^5 )。

算法标签

• 分块
• 有序序列维护
• 行列排序收敛性
• 离线查询与修改

样例验证
样例中查询输出符合推导，修改后查询能正确反映最终形态值。