526互联

CF568E Longest Increasing Subsequence 题解

发布时间 2023-10-19 09:40:42作者: xuantianhao

Longest Increasing Subsequence

LIS 问题有两种主流 \(O(n\log n)\) 解法，最常见的树状数组法，以及不那么常见的二分法。然后考虑本题，发现一个神奇的思路就是求出 LIS 后倒序复原出数组。

进一步思考后发现，因为本题是 LIS（Longest Increasing Subsequence） 而非 LNDS（Longest Non-Decresing Subsequence），所以任意值在 LIS 中只出现一次，所以我们完全可以不用纠结“一个数只能补一个空缺的位置”这个限制，直接忽略它，求出 LIS 时所有在 LIS 中的空缺的填补方法，然后再用尚未被填补的数来补尚未被填补的位置即可。

然后就轮到我们考虑使用哪种 LIS 了。树状数组法似乎不好扩展（除非把每个空位填哪个数都给枚举一遍扔进 BIT 里面，但是这样很明显一共要扔 \(10^3\times10^5=10^8\) 次，单次 \(O(1)\) 还勉强可以，\(O(\log n)\) 你在想桃子），因此我们不妨考虑一下二分法。

于是我们发现二分法是可以的，因为其状态 \(f_i\) 表示长度为 \(i\) 的 LIS 的末尾数最小可能是多少，在非空位处直接二分，在空位处原本也要枚举填哪个数然后二分，但是很明显可以用 two-pointers 轻松 \(O(n)\) 处理。于是复杂度便变为 \(n\log n+k(n+m)\)。

于是我们现在便可以求出 LIS 长度，考虑复原序列。

我们发现肯定要求出一个 \(g_i\) 表示以位置 \(i\) 结尾的 LIS 的最长长度。为了实现快速倒推，还要对非空位处的 \(g\) 求出其前驱位置，记作 \(las_i\)。而 \(las\) 又可以通过在 DP 的过程中对每个 \(f\) 维护该最小的末尾数的位置 \(pos\) 来求出。

于是我们考虑倒推。对于一个非空缺的位置，我们显然可以通过 \(las\) 直接倒推；对于一个空缺的位置，我们考虑优先倒推到非空的位置（这个可以通过枚举得到）；否则，即其无法倒推到非空位置，也即其必倒推到空位，而此时我们肯定想贪心地倒推到最后一个空位，那就倒吧。

时间复杂度如上，即为 \(n\log n+k(n+m)\)。

代码：

#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int N=1e5+100;
int n,m,lim;
int a[N],b[N],f[N],pos[N],g[N],las[N];
multiset<int>s;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    cin>>m;
    for(int i=1;i<=m;i++) cin>>b[i],s.insert(b[i]);
    sort(b+1,b+m+1);
    memset(f,INF,sizeof(f));
	f[0]=0;
    for(int i=1;i<=n;i++){
        if(a[i]!=-1){
            int p=lower_bound(f+1,f+n+1,a[i])-f;
            if(f[p]>a[i]){
				f[p]=a[i];
				pos[p]=i;
			}
            g[i]=p;
			las[i]=pos[p-1];
        }else{
            for(int j=m,k=i;j;j--){
                while(k&&f[k-1]>=b[j])k--;
                if(k&&f[k]>b[j]){
					f[k]=b[j];
					pos[k]=i;
				}
                g[i]=max(g[i],k);
            }
        }
    }
    int i=n;
    while(f[i]==INF) i--;
    for(int j=pos[i],nex=INF;i;i--){
        if(a[j]!=-1){
			nex=a[j];
			j=las[j];
		}else{
            s.erase(s.find(nex=a[j]=*(lower_bound(b+1,b+m+1,nex)-1)));
            bool fd=false;
            for(int k=j-1;k;k--){
				if(a[k]!=-1&&g[k]==i-1&&a[k]<a[j]){
					j=k;
					fd=true;
					break;
				}
			}
            if(fd) continue;
            while(--j) if(a[j]==-1) break;
        }
    }
    for(int i=1;i<=n;i++){
		if(a[i]==-1){
			a[i]=*s.begin();
			s.erase(s.begin());
		}
	}
    for(int i=1;i<=n;i++) cout<<a[i]<<' ';
    return 0;
}