题解：P11244 吻秋

Milky_Cat · 2024-11-03 16:15:12 · 题解

upd：出题人卡了时限使我 cin 过不了了，重修一下。

大家好啊，我是一个蒟蒻，场上因为不会 STL 调试非常久，然后成功被创似了。

因为我是无勾蒟蒻，所以我来讲一个非常非常无脑的做法。

首先丢个结论：对于交换 a_x 和 a_y 的操作，如果满足 a_{x,n} \leq a_{y,1} 或者 a_{y,n} \leq a_{x,1}，就称这次操作是无效的，否则是有效的。可以证明，有效操作不会多于 m^3 次，由于交换操作会交换两个数组，不会多于 \dfrac{m^3}{2} 次，计算可以发现 \dfrac{nm^3}{2} 在 4 \times 10^8 量级，足以通过本题。

证明：

结论 A：交换 1 操作的 x,y，只影响编号而不影响结果，因为元素相同，交换 x,y 与交换操作完之后的 x,y 等价。

结论 B：对 x,y 进行 1 操作后，a_{x,n} \leq a_{y,1}。

然后，对于一对 x,y，假设 x 是操作完 a_i 更小的（由结论 A 可知，x 还是 y 是操作完 a_i 更小的没有影响），显然把 x 和每一个 k \neq x 且 k \neq y 的 k \in [1,m] 都交换一次之后 x 和 y 交换无效（无需考虑把大的放到了 x 里，因为如果对 k,x 排序之后 a_{k,n} \leq a_{x,1}，这时我们会发现 a_{k,n} \leq a_{y,1}，我们实际上可以让 k 顶替 x 的位置）。

在每次操作后，我们都对 x,y 进行一次 1 操作。假设这些操作全部有效，也不会超过 m^3 次。注意到我们每个数组在第一次操作后可以保证完全有序，这样就能实现 O(n) 进行有效操作。

无效操作显然是 O(1) 的，因为无效操作分为两种：

1. 没有贡献。

2. 结果仅仅是交换了两个数组。我们不妨用 f_x 表示第 x 个数组实际上存的是第 f_x 个数组的值，这样可以实现 O(1) 交换。

这样算出来暴力实现有效操作为 nm^3，可以通过。实际上还要小，但是我们这个证明是正确且容易的。

这是复杂度跑满的代码（可以发现能过）：

#include<bits/stdc++.h>
using namespace std;
int a[21][2000003], ta[2000003], tb[2000003], js[23];
bool sd[23];
int jh[23];
int n, m, q;
namespace FastIO {
    char buf[1 << 21], *p1 = buf, *p2 = buf;
#define getchar() (p1 == p2 && (p1 = buf, p2 = (p1 + fread(buf, 1, 1 << 21, stdin))) == p1 ? EOF : *p1++)
    template <typename T> inline T read() { T x = 0, w = 0; char ch = getchar(); while (ch < '0' || ch > '9') w |= (ch == '-'), ch = getchar(); while ('0' <= ch && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar(); return w ? -x : x; }
    template <typename T> inline void write(T x) { if (!x) return; write<T>(x / 10), putchar((x % 10) ^ '0'); }
    template <typename T> inline void print(T x) { if (x > 0) write<T>(x); else if (x < 0) putchar('-'), write<T>(-x); else putchar('0'); }
    template <typename T> inline void print(T x, char en) { print<T>(x), putchar(en); }
}; using namespace FastIO;
#undef getchar()
int main(){
    n = read<int>(), m = read<int>(), q = read<int>();
    for (register int i = 1; i <= m; i++)
        for (register int j = 1; j <= n; j++)
            a[i][j] = read<int>();
    for (register int i = 1; i <= m; i++)   
        jh[i] = i;
    while (q--){
        int op, x, y;
        op = read<int>(), x = read<int>(), y = read<int>();
        if (op == 1){
            int xx = x, yy = y;
            x = jh[x], y = jh[y];
            if (!sd[x])
                sort(a[x] + 1, a[x] + 1 + n);
            if (!sd[y])
                sort(a[y] + 1, a[y] + 1 + n);
            sd[x] = sd[y] = 1;
            js[x]++;
            js[y]++;
            if ((js[x] > m * m / 2 || js[y] > m * m / 2) && a[x][n] <= a[y][1])
                continue;   
            else if ((js[x] > m * m / 2 || js[y] > m * m / 2) && a[y][n] <= a[x][1]){
                swap(jh[xx], jh[yy]);
                continue;
            }
            int p1, p2;
            p1 = 1, p2 = 1;
            for (register int i = 1; i <= n; i++){
                if (p2 > n || (p1 <= n && a[x][p1] < a[y][p2]))
                    ta[i] = a[x][p1++];
                else
                    ta[i] = a[y][p2++];
            }
            for (register int i = 1; i <= n; i++){
                if (p2 > n || (p1 <= n && a[x][p1] < a[y][p2]))
                    tb[i] = a[x][p1++];
                else
                    tb[i] = a[y][p2++];
            }
            for (register int i = 1; i <= n; i++)
                a[x][i] = ta[i], a[y][i] = tb[i];
        }else{
            //x = jh[x];
            print(a[jh[x]][y], '\n');
            //cout <<  << "\n";
        }
    //  for (int i = 1; i <= m; i++)
    //      cout << jh[i] << " ";
    //  cout << "\n";
    //  for (int i = 1; i <= m; i++){
    //      for (int j = 1; j <= n; j++)
    //          cout << a[i][j] << " ";
    //      cout << "\n";
    //  }
    }
    return 0;
}

这是判断是否有效，有效就交换的代码：

#include<bits/stdc++.h>
using namespace std;
int a[23][2000003], ta[2000003], tb[2000003];
bool sd[23];
int jh[23];
int n, m, q;
namespace FastIO {
    char buf[1 << 21], *p1 = buf, *p2 = buf;
#define getchar() (p1 == p2 && (p1 = buf, p2 = (p1 + fread(buf, 1, 1 << 21, stdin))) == p1 ? EOF : *p1++)
    template <typename T> inline T read() { T x = 0, w = 0; char ch = getchar(); while (ch < '0' || ch > '9') w |= (ch == '-'), ch = getchar(); while ('0' <= ch && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar(); return w ? -x : x; }
    template <typename T> inline void write(T x) { if (!x) return; write<T>(x / 10), putchar((x % 10) ^ '0'); }
    template <typename T> inline void print(T x) { if (x > 0) write<T>(x); else if (x < 0) putchar('-'), write<T>(-x); else putchar('0'); }
    template <typename T> inline void print(T x, char en) { print<T>(x), putchar(en); }
}; using namespace FastIO;
#undef getchar()
int main(){
    n = read<int>(), m = read<int>(), q = read<int>();
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            a[i][j] = read<int>();
    for (int i = 1; i <= m; i++)    
        jh[i] = i;
    while (q--){
        int op, x, y;
        op = read<int>(), x = read<int>(), y = read<int>();
        if (op == 1){
            int xx = x, yy = y;
        //  cout << x << " " << y << "\n";
            x = jh[x], y = jh[y];
            if (!sd[x])
                sort(a[x] + 1, a[x] + 1 + n);
            if (!sd[y])
                sort(a[y] + 1, a[y] + 1 + n);
            sd[x] = sd[y] = 1;
        //  cout << op << " " << x << " " << y << "\n";
        //  for (int i = 1; i <= m; i++)
        //      cout << jh[i] << " ";
        //  cout << "\n\n";
            if (a[x][n] <= a[y][1])
                continue;   
            else if (a[y][n] <= a[x][1]){
                swap(jh[xx], jh[yy]);
            //  for (int i = 1; i <= m; i++)
            //      cout << jh[i] << " ";
            //  cout << "\n";
                continue;
            }
        //  for (int i = 1; i <= m; i++)
            //  cout << jh[i] << " ";
        //  cout << "\n";
            int p1 = 1, p2 = 1;
            for (int i = 1; i <= n; i++){
                if (p2 > n || (p1 <= n && a[x][p1] < a[y][p2]))
                    ta[i] = a[x][p1++];
                else
                    ta[i] = a[y][p2++];
            }
            for (int i = 1; i <= n; i++){
                if (p2 > n || (p1 <= n && a[x][p1] < a[y][p2]))
                    tb[i] = a[x][p1++];
                else
                    tb[i] = a[y][p2++];
            }
            for (int i = 1; i <= n; i++)
                a[x][i] = ta[i], a[y][i] = tb[i];
        }else{
            //x = jh[x];
            print(a[jh[x]][y], '\n');
            //cout <<  << "\n";
        }
    //  for (int i = 1; i <= m; i++)
    //      cout << jh[i] << " ";
    //  cout << "\n";
    //  for (int i = 1; i <= m; i++){
    //      for (int j = 1; j <= n; j++)
    //          cout << a[i][j] << " ";
    //      cout << "\n";
    //  }
    }
    return 0;
}