Codeforces

Luogu

分析

考虑普通 LIS 问题的解法，即设 $f_i$ 表示长度为 $i$ 的 LIS 的结尾的最小值，转移时二分即可。

考虑沿用到这道题中。设 $f_i$ 表示长度为 $i$ 的 LIS 的结尾的最小值，$g_i$ 表示长度为 $i$ 的 LIS 的结尾的最小值所在位置；再设 $l_i$ 表示以 $i$ 结尾的 LIS 长度，$p_i$ 表示以 $i$ 结尾的 LIS 上一项所在位置。

另外可以发现相同的数对答案没有影响，所以我们先忽略一个数不能用多次的条件。

为了方便，还可以在末尾加一个 $+\infty$。

考虑转移。分类讨论该数是不是 $-1$：

• 如果该位置不是 $-1$，直接在 $f$ 中二分 $<a_i$ 的最大的值即可。
• 如果该位置是 $-1$，可以枚举这个位置的值，则转化为不是 $-1$ 的情况。事实上这里并不需要二分，用一个指针即可。

考虑还原序列，可以从后往前递推。假设当前的位置为 $pos$，它的值为 $val$，对应的 LIS 长度为 $len$。

先考虑求前一个 $pos$ 仍然分类讨论该数是不是 $-1$：

• 如果该数不是 $-1$，则前一个 $pos$ 为 $p_i$。
• 如果该数是 $-1$，首先找是否存在 $a_j\neq -1,l_j=len-1,a_j<val$，如果存在即上一个位置为 $j$；如果不存在，则上一个位置为上一个 $-1$。

还需要考虑上一个 $pos$ 对应的数是 $-1$ 时求出上一个 $val$。显然它等于 $b$ 中最大的 $<val$ 的数。

然后对于不在 LIS 中的 $-1$，直接设为没有填过的 $b$ 中的数即可。

代码

// ===================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;
const int inf=0x3f3f3f3f;

int n,m,a[N],b[N];
int f[N],g[N],l[N],p[N];
int vis[N],ans[N];

int fd(int w) { return lower_bound(b+1,b+m+1,w)-b-1; }

int main() {
    n=read();
    for (int i=1;i<=n;++i) a[i]=read();
    a[++n]=inf;
    m=read();
    for (int i=1;i<=m;++i) b[i]=read();
    sort(b+1,b+m+1);
    for (int i=1;i<=n;++i) f[i]=inf;
    for (int i=1;i<=n;++i) {
        if (~a[i]) {
            int j=lower_bound(f+1,f+n+1,a[i])-f-1;
            l[i]=j+1,p[i]=g[j],f[j+1]=a[i],g[j+1]=i;
        } else {
            for (int x=m,j=n;x;--x) {
                while (f[j]>=b[x]) --j;
                f[j+1]=b[x],g[j+1]=i;
            }
        }
    }
    for (int len=l[n],pos=n,val=a[n];len;--len) {
        if (~a[pos]) {
            if (~a[p[pos]]) pos=p[pos],val=a[pos];
            else { int t=fd(a[pos]);
                vis[t]=1,pos=p[pos],val=ans[pos]=b[t];
            }
        } else {
            int flag=0;
            for (int k=pos-1;k;--k)
                if (~a[k]&&a[k]<val&&l[k]==len-1) {
                    pos=k,val=a[k]; flag=1; break;
                }
            if (flag) continue;
            for (int k=pos-1;k;--k)
                if (!~a[k]) { int t=fd(val);
                    vis[t]=1,pos=k,val=ans[pos]=b[t]; break;
                }
        }
    }
    for (int i=1,j=1;i<=n;++i) {
        if (~a[i]) ans[i]=a[i];
        else if (!ans[i]) {
            while (vis[j]) ++j;
            vis[j]=1,ans[i]=b[j];
        }
    }
    for (int i=1;i<n;++i) printf("%d%c",ans[i]," \n"[i==n-1]);
    return 0;
}