题解：P11244 吻秋

· · 题解

P11244 吻秋

Part.1 题意描述

给你 m 个数组，每个数组有 n 个元素。

每次要么选两个数组一起排序，然后把小的一半放到 a ，大的一半放到 b 。

要么询问第 i 个数组中第 j 号元素的值。

Part.2 思路分析

我会暴力！

我们可以模拟这个过程。

具体的，每次用 vector 存储每个序列， 1 操作相当于是全部放到另一个 vector 里，然后暴力 sort。

复杂度 O(qn\log n) ，可以获得 9pts。

我会归并排序！

我们发现，每个序列，一旦被使用过 1 操作，那么以后其内容一定是有序的。

因此记录一个数组，表示这个序列曾经是否被排序过。

这个时候，考虑对两个有序的数组进行排序，直接使用归并排序，复杂度少了一个 \log 。

我会优化！（观察到诈骗性质）

这个题目有个有意思的诈骗性质，在于有效的 1 操作不会太多。

考虑对两个有序数组归并排序的实质。

我们发现，这样的归并排序相当于确定两个数组的大小关系。

而在最坏情况下，我们可以类似于冒泡排序的想法，冒泡排序每次交换都会确定两个数的位置，对于 n 个数的数组，最多只会进行 n ^ 2 次排序。

因此，我们可以断言，归并排序的次数不会超过 m ^ 2 。

具体的，我们可以定义 L_i 表示 i 数组的最小值， R_i 表示最大值。

此时对于形如:

1 x y

的操作，我们先判断 x,y 是否有序，如果全部有序，进行分类：

那么我们可以记 p_i 表示 第 i 个数组应为哪一个数组，想要交换 x,y 时，交换 p_x 和 p_y 即可。

Part.3 诈骗性质证明 & 复杂度分析

先来证明一下，为什么经过最多 m ^ 2 次归并排序，不会再次进行有效的排序。

还是考虑 1 操作实质是干了什么。

对于序列 a,b 我们发现进行 1 操作，只不过是把所有元素里面较小的归为一个，较大的归入另一个。

而我们如果把 a,b,c 两两进行 1 操作：

更多个序列同理。

因此，真正有意义的排序操作不会多于两两操作的次数，即 \dfrac{ m \times (m - 1) }{ 2 } 次。

综上所述，我们做了 m 次 sort，又做了 m ^ 2 次归并，之后的操作只有交换下标 p_i。

时间复杂度为 O(nm \log nm + nm^2 + q)。

视 \log nm 与 m 同阶，复杂度为 O(nm^2) 。

Part.4代码实现

#include<bits/stdc++.h>
using namespace std;
const int N = 25;
vector<int> a[N];
int p[N],L[N],R[N],n,m,q; // p[i] 表示具体为哪个序列
// 第 i 个序列实际上是 a[p[i]]
bool sorted[N]; // 表示是否已经 sort 过

inline void Merge(int x,int y){ // 归并
    vector<int> ans;
    int Lpos = 0,Rpos = 0;
    while(Lpos < n && Rpos < n){
        if(a[p[x]][Lpos] < a[p[y]][Rpos]){
            ans.push_back(a[p[x]][Lpos]);
            Lpos ++;
        }
        else{
            ans.push_back(a[p[y]][Rpos]);
            Rpos ++;
        }
    }
    while(Lpos < n){
        ans.push_back(a[p[x]][Lpos]);
        Lpos ++;
    }
    while(Rpos < n){
        ans.push_back(a[p[y]][Rpos]);
        Rpos ++;
    }
    a[p[x]].clear(),a[p[y]].clear();
    for(int i = 0;i < n;++ i) a[p[x]].push_back(ans[i]);
    for(int i = n;i < n + n;++ i) a[p[y]].push_back(ans[i]);
    L[p[x]] = a[p[x]][0],R[p[x]] = a[p[x]][n - 1];
    L[p[y]] = a[p[y]][0],R[p[y]] = a[p[y]][n - 1];
}

inline void Sort(int x,int y){ // 暴力排序
    vector<int> ans;
    for(int k : a[p[x]]) ans.push_back(k);
    for(int k : a[p[y]]) ans.push_back(k);
    sort(ans.begin(),ans.end());
    a[p[x]].clear(),a[p[y]].clear();
    sorted[x] = sorted[y] = true;
    for(int i = 0;i < n;++ i) a[p[x]].push_back(ans[i]);
    for(int i = n;i < n + n;++ i) a[p[y]].push_back(ans[i]);
    L[p[x]] = a[p[x]][0],R[p[x]] = a[p[x]][n - 1];
    L[p[y]] = a[p[y]][0],R[p[y]] = a[p[y]][n - 1];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>q;
    for(int i = 1;i <= m;++ i){
        p[i] = i;
        sorted[i] = false;
        for(int j = 1;j <= n;++ j){
            int x;
            cin>>x;
            a[i].push_back(x);
        }
    }
    while(q --){
        int op;
        cin>>op;
        switch(op){
            case(1):{
                int x,y;
                cin>>x>>y;
                if(sorted[p[x]] && sorted[p[y]]){
                    if(R[p[x]] <= L[p[y]]) break; // 如果这次操作不会有任何事发生，直接跳过
                    else if(R[p[y]] <= L[p[x]]) swap(p[x],p[y]); // 两个序列中的值错开，可以直接交换下标
                    else Merge(x,y); // 可以进行归并排序
                }
                else Sort(x,y); // 存在乱序序列，只能暴力排序
                break;
            }
            case(2):{
                int x,y;
                cin>>x>>y;
                cout<<a[p[x]][y - 1]<<"\n";
                break;
            }
            default: break;
        }
    }
    return 0;
}