自动搬运

查看原文

来自洛谷，原作者为

	zichen3004 为什么这么菜啊

搬运于2025-08-24 23:05:39，当前版本为作者最后更新于2024-11-02 18:25:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

非常好诈骗题，使我的大脑旋转。

观察到 $m \le 20$，显然是降低时间复杂度的重要结论，如果你分析过 selection sort 的最大比较次数就会发现应该是在 $O(M^2)$ 量级的*，所以有效的归并次数不会多于 $400$ 次，归并这块的总复杂度 $O(NM^2)$ 完全可以接受。

考虑 quick sort 的次数，每个序列至多一次 quick sort，所以这块的时间复杂度应该是 $O(NM \log N)$，同样可以接受。

最后考虑怎么处理两个“绝对有序”的序列，即可以通过拼接获得有序序列的两个序列。这样的序列无需内部排序，设原本序列为 $S_1$，$S_2$。如果原本 $S_1+S_2$ 就有序的话，无需进行操作，否则 $S_2+S_1$ 有序，交换 $S_1$，$S_2$ 即可。

如果直接交换复杂度是 $O(NQ)$ 的，不能接受。开一个 $NowPos$ 记录当前行实际在第几行，如果要交换两行 $i$，$j$ 直接交换 $NowPos_i$，$NowPos_j$ 即可，复杂度降到 $O(Q)$。

最终复杂度为以上三部分复杂度最大值，要注意的是输入数据确实很大，注意快读快写。

最后献上赛时代码，代码不短但是很好写。

#include<bits/stdc++.h>
using namespace std;
int n, m, q;
int ifFinishSort[25], NowPos[25];
vector<int> vec[21];

void read(int &x){
    x=0;int flg=1;char ch=getchar();
    for(;ch<'0'||ch>'9';) {if(ch=='-') flg=-1;ch=getchar();}
    for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
    x=x*flg;
}

void write(int x)
{
    if(x<0)
        putchar('-'),x=-x;
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
    return;
}

void Merge(int X, int Y)
{
	int TrueX = NowPos[X], TrueY = NowPos[Y];
	vector<int> TmpArray;
	int i = 0, j = 0; 
	if(!ifFinishSort[X])
		sort(vec[TrueX].begin(), vec[TrueX].end()), ifFinishSort[X] = true;
	if(!ifFinishSort[Y])
		sort(vec[TrueY].begin(), vec[TrueY].end()), ifFinishSort[Y] = true;
	while(i < n && j < n)
		TmpArray.emplace_back(vec[TrueX][i] < vec[TrueY][j] ? vec[TrueX][i++] : vec[TrueY][j++]);
	while(i < n)
		TmpArray.emplace_back(vec[TrueX][i++]);
	while(j < n)
		TmpArray.emplace_back(vec[TrueY][j++]);
	for(int i = 0; i < n; i++)
		vec[TrueX][i] = TmpArray[i];
	for(int i = n; i < (n << 1); i++)
		vec[TrueY][i - n] = TmpArray[i];
}

void DealWithSortedArrayAndExchange(int X, int Y)
{
	int TrueX = NowPos[X], TrueY = NowPos[Y];
	if(vec[TrueX][n - 1] <= vec[TrueY][0])
		return;
	if(vec[TrueX][0] >= vec[TrueY][n - 1])
	{
		swap(NowPos[X], NowPos[Y]);
		return;
	}
	Merge(X, Y);
}

int tmp;

int main()
{
	read(n), read(m), read(q);
	for(int i = 1; i <= m; i++)
		ifFinishSort[i] = false, NowPos[i] = i;
	for(int i = 1; i <= m; i++)
		for(int j = 1; j <= n; j++)
			read(tmp), vec[i].emplace_back(tmp);
	while(q--)
	{
		int opt, u, v; read(opt), read(u), read(v);
		if(opt == 1)
		{
			if(!ifFinishSort[u] || !ifFinishSort[v])
				Merge(u, v);
			else
				DealWithSortedArrayAndExchange(u, v);
//			for(int i = 1; i <= m; i++)
//			{
//				for(int j = 0; j < n; j++)
//					cout << vec[NowPos[i]][j] << ' ';
//				cout << endl;
//			}
		}
		if(opt == 2)
		{
			write(vec[NowPos[u]][v - 1]), putchar('\n');
		}
	}
	return 0;
}

$^*$ 考虑为什么在 $M^2$ 的时间复杂度中可以完成排序，使得任意两行“绝对有序”：

对于任意两行可以交换他们的位置，因此我们不妨设最后 $S_1+S_2+…+S_m$ 有序，操作保证 $i < j$。

不同的整数对 $(i, j)$ 有 $\frac{(m-1)m}{2}$ 个，所以我们可以保证 $M^2$ 量级内每一个序列都被选中，即变得内部有序。

而我们发现，对于第一行，我们能在 $M - 1$ 次操作以内使其变成：

1 2 3 … n

因为执行完一次操作后，就会新增一组关于 $S_1$ 的绝对有序, $M - 1$ 组绝对有序，即全局绝对有序，保证了其最小的形态。

考虑其他操作是否会使关于 $S_1$ 绝对有序的数量减少。

假设原本 $S_1$ 和 $S_u$ 绝对有序，$S_1$ 和 $S_v$ 绝对有序，操作后 $S_1$ 和 $S_u$，$S_v$ 一定还都是绝对有序的。

假设原本 $S_1$ 和 $S_u$ 绝对有序，$S_1$ 和 $S_v$ 非绝对有序，操作后，$S_1$ 和 $S_v$ 绝对有序，因为 $S_u$ 里有 $n$ 个大于 $S_{1, n}$ 的数字，所以总共大于 $S_{1, n}$ 的数字数量不少于 $n$ 个，其中最大的 $n$ 个会全部有序地排在 $S_v$ 中。

其他行同理，注意我们只考虑当前行 $S_u$ 绝对小于 $S_v(u<v)$，与前面行的关系由前面行保证，因此操作次数 $T\le\frac{(m-1)m}{2}$。