【题解】P11244 吻秋

qW__Wp · 2024-11-03 10:29:28 · 题解

是的，这很诈骗。

如果是暴力归并，需要排序 m 次，合并 q 次，时间复杂度 O(m \times n \log n + q \times n)，无法接受。

排序部分是无需优化的，考虑优化合并部分。发现如果两个数组本身就有序，且其中一个数组的最大值 \le 另一个数组的最小值，那么就不需要合并，进行：

• 若 \max \{x_i\} \le \min \{y_i\}，则不用操作。

• 若 \max \{y_i\} \le \min \{x_i\}，则交换 x 和 y。

这样一来，最多只会合并 m^2 次（关于这个，我不会证，可以感性理解：任意一个数组都与其他所有数组合并过，那么任意两个数组都满足上述性质，无需再合并），时间复杂度 O(n m^2)。

但是交换数组的时间复杂度是 O(n) 的，怎么办？

真的是 O(n) 的吗？其实如果使用 C++ 的 vector，使用 swap 交换容器是 O(1) 的（有兴趣的可以 bdfs），于是我们可以使用 vector 存储。

时间复杂度 O(m \times n \log n + n m ^ 2 + q)，足以通过（甚至不用快读快输，关闭同步流后仅需 1s 不到即可跑过最大数据）。

Code:

#include <bits/stdc++.h>
//#define int long long
#define INF 0x3fffffff
#define INFF 1e18
#define endl '\n'
#define lson id << 1
#define rson id << 1 | 1
#define LL long long
#define ULL unsigned long long

using namespace std;

const int N = 1e6 + 5;

vector<int> a[25];
int b[N << 1];
bool f[N], v[N];

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, m, q; cin >> m >> n >> q;
    for (int i = 1; i <= n; i ++) {
        a[i].push_back(0);
        for (int j = 1; j <= m; j ++) {
            int x; cin >> x;
            a[i].push_back(x);
        }
    }
    while (q --) {
        int op, x, y; cin >> op >> x >> y;
        if (op == 1) {
            if (f[x] && f[y]) {
                if (a[x][1] >= a[y][m]) {
                    swap(a[x], a[y]);
                    continue;
                } else if (a[x][m] <= a[y][1]) {
                    continue;
                }
            }
            if (!f[x]) sort(a[x].begin(), a[x].end());
            if (!f[y]) sort(a[y].begin(), a[y].end());
            f[x] = f[y] = 1;
            int i = 1, j = 1, cnt = 0;
            while (i <= m || j <= m) {
                if (i <= m && (j > m || a[x][i] <= a[y][j]))
                    b[ ++ cnt] = a[x][i ++];
                else b[ ++ cnt] = a[y][j ++];
            }
            for (int i = 1; i <= cnt; i ++) {
                if (i <= m) a[x][i] = b[i];
                else a[y][i - m] = b[i];
            }
        } else {
            cout << a[x][y] << endl;
        }
    }
    return 0;
}