P11244 吻秋题解

lun_hao · 2024-11-04 08:12:42 · 题解

洛谷题目传送门

博客园可能食用更佳

题目大意：

给你 m 个长度为 n 的序列 a，Q 次操作：

1 x y 将 a_x 与 a_y 的所有元素取出至长度为 2n 的序列 b，将 b 升序重排后 a_x \gets b_{1 \dots n},a_y \gets b_{n+1 \dots 2n}；
2 i j 询问 a_{i,j} 的值。

数据范围：1 \leq nm \leq 10^6,\color{red} 1 \leq m \leq 20 \color{black} ,1 \leq Q \leq 4 \times 10^5

题目分析：

~~赛时莫名其妙就 AC 了，赛后算时间复杂度才发现自己被诈骗了。~~

由于数据范围给定的是 nm 的大范围，故考虑开 vector 存 a_{1 \dots m} 序列，这里埋下伏笔。

首先肯定不能按照提题意直接硬做，考虑发现一下有没有什么人类智慧。

观察到操作 1 可以等价为将 a_x,a_y 升序排序后再归并，若 a_x,a_y 已经排过序了，并且发现在后续的操作中都不会使得元素的相对大小发生改变，故每个序列 a_i 最多只会被排序一次，开个桶记录一下，时间复杂度为 \mathcal O(m n \log n)。

继续观察，发现 m 很小，并且对这 m 个序列两两之间进行操作 1 后，会发现 a 会趋近于稳定的状态，即两两之间操作共 \frac{m(m-1)}{2} 次后，\forall i,j \in [1,m] \cap \mathbb Z,i<j，都有 a_i 中所有的元素小于等于 a_j 中所有的元素，这部分时间复杂度为 \mathcal O(m^2 n)。

进行完上面的操作之后就可以不用归并直接判断是否需要交换就行，因为 vector 进行 swap 操作是常数复杂度，而非线性，故时间复杂度为 \mathcal O(Q)。

综上所得，总的时间复杂度为 \mathcal O(m n \log n +m^2 n+Q)，足以通过此题。

有些细节见代码。

Code：

#include<bits/stdc++.h>
#define re register
#define il inline
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?0:*p1++)
using namespace std;
//快读快写 
char buf[1<<20],*p1,*p2;
il int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48),ch=getchar();}return x*f;}
il void write(int x){if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+48);}
const int M=25,INF=0x3f3f3f3f;
int n,m,q;
vector<int> a[M],b;
bool used[M];
il void solve()
{
    int opt=read(),x=read(),y=read();
    if(opt==2) return write(a[x][y]),putchar('\n'),void();
    //这里简写了，等同于： 
    /*
        if(opt==2)
        {
            write(a[x][y]),putchar('\n');
            return;
        }
    */
    // step 1 排序 
    if(!used[x]) sort(a[x].begin(),a[x].end()),used[x]=1;
    if(!used[y]) sort(a[y].begin(),a[y].end()),used[y]=1;
    // step 3 直接交换 
    int minx=a[x][1],maxx=a[x][n];
    int miny=a[y][1],maxy=a[y][n];
    //判断 a_x 中所有元素是否都小于 a_y 中所有元素可以直接用 a_x 的最大值与 a_y 的最小值比较即可
    //因为已经排序，最大最小值在首尾取到即可 
    if(maxx<=miny) return;
    if(maxy<=minx) return swap(a[x],a[y]),void();
    // step 2 归并 
    int i=1,j=1,k=0;
    while(i<=n&&j<=n)
    {
        if(a[x][i]<=a[y][j]) b[++k]=a[x][i++];
            else b[++k]=a[y][j++];      
    }
    while(i<=n) b[++k]=a[x][i++];
    while(j<=n) b[++k]=a[y][j++];
    for(re int i=1;i<=n;i++) a[x][i]=b[i];
    for(re int i=n+1;i<=n+n;i++) a[y][i-n]=b[i];
}
int main()
{
    n=read(),m=read(),q=read();
    for(re int i=1;i<=m;i++) a[i].resize(n+1);//初始化 vector 大小 
    for(re int i=1;i<=m;i++)
        for(re int j=1;j<=n;j++) a[i][j]=read();//注意从下标 1 开始读入，方便后面的排序 
    b.resize(n*2+1);
    while(q--) solve();
    return 0;
}

P11244 吻秋 题解

题目大意：

题目分析：

Code：

P11244 吻秋题解