题解：P11244 吻秋

D0000 · 2024-11-02 19:54:54 · 题解

这道题如果就按照题目描述所说的办法做，就是一个 O(mn\log n+nq) 的做法，可以开心地获得 9 分。

那么正解事实上是从性质 m\le20 出发的，并且发现若 x,y 排一次序后，再排一次 x,y 不会有任何变化，排一次 y,x 则完全交换二者。于是可以推断有效的操作次数不会太多，再猜应该是个 O(m^2)。

记 b_{x,y}=1 当所有 a_{x,i} 都小于 a_{y,j}。顺着处理 b_{x,y}=b_{y,x}=0 时如何交换 x,y。先排一遍序，再发现原先 b_{x,i},b_{i,y} 的状态可以保留，因为 x 不会再变大，y 不会再变小。而 b_{y,i},b_{i,x} 的状态需要分别给到 b_{x,i},b_{i,y} 就行了。最后再让 b_{x,y}=1 即可。

只有当 b_{x,y}=0 时才会进行排序，而每次排完序后会多一个 b_{x,y}=1，因此总共排序不会超过 \frac{m\times(m-1)}{2} 次。

总时间复杂度 O(m^2n)。

代码：

#include<cstdio>
#include<vector>
#include<utility>
#include<algorithm>
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;
int a[21][2000001],aa[4000001],a2[21][2000001];
bool b[21],bb[21][21];
int p[21];
int main(){
    int n=read<int>(),m=read<int>(),q=read<int>();
    for(int i=1;i<=m;i++){p[i]=i;
        for(int j=1;j<=n;j++)a[i][j]=read<int>(),aa[j]=a[i][j];
        std::sort(aa+1,aa+n+1);
        for(int j=1;j<=n;j++)a2[i][j]=aa[j];
    }
    while(q--){
        int op=read<int>(),x=read<int>(),y=read<int>();
        if(op==1){
            int xx=x,yy=y;
            x=p[x],y=p[y];
            if(bb[x][y])continue;
            if(bb[y][x]){
                std::swap(p[xx],p[yy]);
                continue;
            }
            b[x]=b[y]=1;
            int cnt=1,i=1,j=1;
            while(i<=n&&j<=n){
                if(a2[x][i]<a2[y][j])aa[cnt++]=a2[x][i++];
                else aa[cnt++]=a2[y][j++];
            }
            while(i<=n)aa[cnt++]=a2[x][i++];
            while(j<=n)aa[cnt++]=a2[y][j++];
            for(i=1;i<=n;i++)a2[x][i]=aa[i],a2[y][i]=aa[i+n];
            for(i=1;i<=m;i++)if(i!=x&&i!=y)bb[i][y]|=bb[i][x],bb[x][i]|=bb[y][i],bb[i][x]=0,bb[y][i]=0;
            bb[x][y]=1;
        }
        else print((b[x]?(a2[p[x]][y]):(a[p[x]][y])),'\n');
    }
}