博客园可能食用更佳
题目大意：
给你 m m m 个长度为 n n n 的序列 a a a， Q Q Q 次操作：
-
1 x y将 a x a_x ax 与 a y a_y ay 的所有元素取出至长度为 2 n 2n 2n 的序列 b b b，将 b b b 升序重排后 a x ← b 1 … n , a y ← b n + 1 … 2 n a_x \gets b_{1 \dots n},a_y \gets b_{n+1 \dots 2n} ax←b1…n,ay←bn+1…2n； -
2 i j询问 a i , j a_{i,j} ai,j 的值。
数据范围： 1 ≤ n m ≤ 1 0 6 , 1 ≤ m ≤ 20 , 1 ≤ Q ≤ 4 × 1 0 5 1 \leq nm \leq 10^6,\color{red} 1 \leq m \leq 20 \color{black} ,1 \leq Q \leq 4 \times 10^5 1≤nm≤106,1≤m≤20,1≤Q≤4×105
题目分析：
赛时莫名其妙就 AC 了，赛后算时间复杂度才发现自己被诈骗了。
由于数据范围给定的是
n
m
nm
nm 的大范围，故考虑开 vector 存
a
1
…
m
a_{1 \dots m}
a1…m 序列，这里埋下伏笔。
首先肯定不能按照提题意直接硬做，考虑发现一下有没有什么人类智慧。
观察到操作 1 1 1 可以等价为将 a x , a y a_x,a_y ax,ay 升序排序后再归并，若 a x , a y a_x,a_y ax,ay 已经排过序了，并且发现在后续的操作中都不会使得元素的相对大小发生改变，故每个序列 a i a_i ai 最多只会被排序一次，开个桶记录一下，时间复杂度为 O ( m n log n ) \mathcal O(m n \log n) O(mnlogn)。
继续观察，发现 m m m 很小，并且对这 m m m 个序列两两之间进行操作 1 1 1 后，会发现 a a a 会趋近于稳定的状态，即两两之间操作共 m ( m − 1 ) 2 \frac{m(m-1)}{2} 2m(m−1) 次后， ∀ i , j ∈ [ 1 , m ] ∩ Z , i < j \forall i,j \in [1,m] \cap \mathbb Z,i<j ∀i,j∈[1,m]∩Z,i<j，都有 a i a_i ai 中所有的元素小于等于 a j a_j aj 中所有的元素，这部分时间复杂度为 O ( m 2 n ) \mathcal O(m^2 n) O(m2n)。
进行完上面的操作之后就可以不用归并直接判断是否需要交换就行，因为 vector 进行 swap 操作是常数复杂度，而非线性，故时间复杂度为
O
(
Q
)
\mathcal O(Q)
O(Q)。
综上所得，总的时间复杂度为 O ( m n log n + m 2 n + Q ) \mathcal O(m n \log n +m^2 n+Q) O(mnlogn+m2n+Q)，足以通过此题。
有些细节见代码。
Code：
#include<bits/stdc++.h>
#define re register
#define il inline
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?0:*p1++)
using namespace std;
//快读快写
char buf[1<<20],*p1,*p2;
il int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48),ch=getchar();}return x*f;}
il void write(int x){if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+48);}
const int M=25,INF=0x3f3f3f3f;
int n,m,q;
vector<int> a[M],b;
bool used[M];
il void solve()
{
int opt=read(),x=read(),y=read();
if(opt==2) return write(a[x][y]),putchar('\n'),void();
//这里简写了，等同于：
/*
if(opt==2)
{
write(a[x][y]),putchar('\n');
return;
}
*/
// step 1 排序
if(!used[x]) sort(a[x].begin(),a[x].end()),used[x]=1;
if(!used[y]) sort(a[y].begin(),a[y].end()),used[y]=1;
// step 3 直接交换
int minx=a[x][1],maxx=a[x][n];
int miny=a[y][1],maxy=a[y][n];
//判断 a_x 中所有元素是否都小于 a_y 中所有元素可以直接用 a_x 的最大值与 a_y 的最小值比较即可
//因为已经排序，最大最小值在首尾取到即可
if(maxx<=miny) return;
if(maxy<=minx) return swap(a[x],a[y]),void();
// step 2 归并
int i=1,j=1,k=0;
while(i<=n&&j<=n)
{
if(a[x][i]<=a[y][j]) b[++k]=a[x][i++];
else b[++k]=a[y][j++];
}
while(i<=n) b[++k]=a[x][i++];
while(j<=n) b[++k]=a[y][j++];
for(re int i=1;i<=n;i++) a[x][i]=b[i];
for(re int i=n+1;i<=n+n;i++) a[y][i-n]=b[i];
}
int main()
{
n=read(),m=read(),q=read();
for(re int i=1;i<=m;i++) a[i].resize(n+1);//初始化 vector 大小
for(re int i=1;i<=m;i++)
for(re int j=1;j<=n;j++) a[i][j]=read();//注意从下标 1 开始读入，方便后面的排序
b.resize(n*2+1);
while(q--) solve();
return 0;
}