P11244

HasNoName · 2024-11-03 10:45:39 · 题解

思路

先考虑怎么用 O(N) 的时间完成一次 1 操作。

可以证明，将两个序列合并后排序再拆开一定也是两个有序的数组。

所以一开始先把所有数组排序，如果一次询问的数组在之前进行过操作，则这个数组一定有序，否则将原数组备份的数组中的答案输出。

再使用归并排序中的方法可以做到 O(N) 排序。

考虑到两个数组合并时如果拼起来已经有序，则不用操作；如果将两个数组的顺序调换，则每次只用交换两个数组的下标，用一个数组记录下标即可。这两种情况复杂度 O(1)。否则用 O(N) 的时间合并。

由于两个数组进行一次操作后一定可以使数组有一种方法拼起来后有序，最多对一个数组进行 M-1 此有效操作后，其他所有的序列和它进行操作都无法进行有效操作。

所以至多进行 M(M-1) 此操作可以让所有数组可以以一种方式连成一个数组，且单调不降。

综上，我们可以用 O(M^2N) 的复杂度解决这题。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2000005,Q=5e6+5;
int tmp[2*N],tag[25],p[25];
vector<int>a[25],b[25];
int opp[Q],uu[Q],vv[Q],t[25];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m,T;
    cin>>n>>m>>T;
    for(int i=1;i<=m;i++)
    {
        a[i].push_back(0);
        b[i].push_back(0);
        for(int j=1;j<=n;j++)
        {
            int x;
            cin>>x;
            a[i].push_back(x);
            b[i].push_back(x);
        }
        sort(a[i].begin(),a[i].end());
        p[i]=i;
    }
    int op,u,v,last=0,cnt=0;
    for(int i=1;i<=T;i++)
    {
        cin>>opp[i]>>uu[i]>>vv[i];
        if(opp[i]==2)
        {
            t[uu[i]]=1;
            last=i;
            cnt++;
        }
    }
    if(cnt==1)return 0;
    for(int i=1;i<=last;i++)
    {
        op=opp[i];u=uu[i];v=vv[i];
        int &x=p[u];
        if(op==1)
        {
            //if(!t[u]&&!t[v])continue;
            int &y=p[v];
            if(a[x][n]<=a[y][1])continue;
            if(a[y][n]<=a[x][1])
            {
                swap(x,y);
                continue;
            }
            int l1=1,l2=1;
            for(int i=1;i<=n+n;i++)
            {
                if(l1==n+1)tmp[i]=a[y][l2++];
                else if(l2==n+1)tmp[i]=a[x][l1++];
                else if(a[x][l1]<a[y][l2])tmp[i]=a[x][l1++];
                else tmp[i]=a[y][l2++];
            }
            for(int i=1;i<=n;i++)
            {
                a[x][i]=tmp[i];
                a[y][i]=tmp[i+n];
            }
            tag[x]=1;
            tag[y]=1;
        }
        else
        {
            if(!tag[u])cout<<b[x][v]<<'\n';
            else cout<<a[x][v]<<'\n';
        }
    }
    return 0;
}