题解：P11244 吻秋
gyyyyx
·
·
题解
诈骗题。
看着很复杂，赛事想了很多做法都不行，然后就去睡觉了。
睡醒比赛结束之后再想了想发现就是个诈骗题。
显然可以将所有数组都先排好序，下面假定所有数组都是单调不降的。
如果两个数组 a_x,a_y 直接合并起来就是单调不降的，我们称 a_x<a_y,a_y>a_x。
如果两个数组 a_x,a_y 满足 a_x<a_y 或者 a_x>a_y，那么称这两个数组不相交；反之我们称这两个数组相交。
我们设 c_x 为小于第 x 个数组的数组的数量。
对于操作一，操作完后必然满足 a_x<a_y。
那么如果 a_x<a_y 那么操作就相当于作废；如果 a_x>a_y 那么操作相当于交换 a_x,a_y 同时也要交换 c_x,c_y。
而对于其他情况，操作完之后 a_x<a_y，那么c_y 加 1。
发现了什么？
$c$ 数组的和最大为 $\frac{m(m-1)}{2}$，也就是任意两个数组都不相交的时候。
由于 $m\leq 20$，这启示我们当 $a_x,a_y$ 相交的时候暴力归并，这样最多处理 $O(m^2)$ 次；而剩余情况是 $a_x,a_y$ 不相交，这样的操作一是可以 $O(1)$ 完成的。
操作二查询是简单的，不多赘述。
最后时间复杂度 $O(mn\log n+m^2n+q)$。
感觉归并会快一点但为什么好像直接快排的 $O(mn+m^2n\log n+q)$ 还更快（大雾）。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x(0),flg(1);char c(getchar());
while(c<'0'||c>'9'){if(c=='-') flg=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return x*flg;
}
void write(int x){
if(x>9) write(x/10);
putchar(x%10^48);
}
int n,m,q;
vector <int> a[25],b;
int flg[25],id[25];
int main(){
n=read();m=read();q=read();
for(int i(1);i<=m;++i) id[i]=i;
for(int i(1);i<=m;++i)
for(int j(0);j<n;++j)
a[i].push_back(read());
b.resize(n<<1);
while(q--){
int op(read()),x(read()),y(read());
if(op==1){
if(!flg[id[x]]) sort(a[id[x]].begin(),a[id[x]].end()),flg[id[x]]=1;
if(!flg[id[y]]) sort(a[id[y]].begin(),a[id[y]].end()),flg[id[y]]=1;
if(a[id[x]][n-1]<=a[id[y]][0]) continue;
if(a[id[y]][n-1]<=a[id[x]][0]){
swap(id[x],id[y]);
continue;
}
x=id[x];y=id[y];
for(int i(0),j(0),k(0);i<n;++i){
while(j<n&&a[y][j]<a[x][i]) b[k++]=a[y][j++];
b[k++]=a[x][i];
if(i==n-1) while(j<n) b[k++]=a[y][j++];
}
for(int i(0);i<n;++i) a[x][i]=b[i],a[y][i]=b[i+n];
}
else write(a[id[x]][y-1]),puts("");
}
return 0;
}
```