题解：P11244 吻秋

zichen3004 · 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;
}