博客园可能食用更佳
题目大意：
给你 \(m\) 个长度为 \(n\) 的序列 \(a\)，\(Q\) 次操作：
-
1 x y将 \(a_x\) 与 \(a_y\) 的所有元素取出至长度为 \(2n\) 的序列 \(b\)，将 \(b\) 升序重排后 \(a_x \gets b_{1 \dots n},a_y \gets b_{n+1 \dots 2n}\)； -
2 i j询问 \(a_{i,j}\) 的值。
数据范围：\(1 \leq nm \leq 10^6,\color{red} 1 \leq m \leq 20 \color{black} ,1 \leq Q \leq 4 \times 10^5\)
题目分析：
赛时莫名其妙就 AC 了，赛后算时间复杂度才发现自己被诈骗了。
由于数据范围给定的是 \(nm\) 的大范围，故考虑开 vector 存 \(a_{1 \dots m}\) 序列，这里埋下伏笔。
首先肯定不能按照提题意直接硬做，考虑发现一下有没有什么人类智慧。
观察到操作 \(1\) 可以等价为将 \(a_x,a_y\) 升序排序后再归并，若 \(a_x,a_y\) 已经排过序了，并且发现在后续的操作中都不会使得元素的相对大小发生改变，故每个序列 \(a_i\) 最多只会被排序一次，开个桶记录一下，时间复杂度为 \(\mathcal O(m n \log n)\)。
继续观察，发现 \(m\) 很小，并且对这 \(m\) 个序列两两之间进行操作 \(1\) 后，会发现 \(a\) 会趋近于稳定的状态，即两两之间操作共 \(\frac{m(m-1)}{2}\) 次后，\(\forall i,j \in [1,m] \cap \mathbb Z,i<j\)，都有 \(a_i\) 中所有的元素小于等于 \(a_j\) 中所有的元素，这部分时间复杂度为 \(\mathcal O(m^2 n)\)。
进行完上面的操作之后就可以不用归并直接判断是否需要交换就行，因为 vector 进行 swap 操作是常数复杂度，而非线性，故时间复杂度为 \(\mathcal O(Q)\)。
综上所得，总的时间复杂度为 \(\mathcal O(m n \log n +m^2 n+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;
}