分析
考虑普通 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;
}