解：考场上爆0了......
回想怎么求两个排列的最长公共子序列。
回想怎么求1~n每个数恰出现两次的两个序列的最长公共子序列。就是每个数替换为它在另一个序列里的出现位置，降序。
所以我们可以把这每个空位都倒序填入m个数，然后暴力，最后输出方案。
考虑优化。发现在每个空位的时候，这m个数都是单降的。直接拿指针在单调栈上扫，可以O(top + m)转移。
关于记录方案，每个位置记录以它结尾的lis中的前一个非-1位置，以及在这之间有多少个-1。
然后就可以把空间优化到O(n)。
#include <bits/stdc++.h> typedef long long LL;
const int N = ;
const LL INF = 0x3f3f3f3f3f3f3f3fll;; struct Node {
int a, b;
Node(int A = , int B = ) {
a = A;
b = B;
}
}frp[N], fr[N]; LL a[N], b[N], p[N];
int top, n, m;
bool vis[N]; int main() {
scanf("%d", &n);
for(int i = ; i <= n; i++) {
scanf("%lld", &a[i]);
}
scanf("%d", &m);
for(int i = ; i <= m; i++) {
scanf("%lld", &b[i]);
}
std::sort(b + , b + m + );
std::reverse(b + , b + m + );
a[n + ] = INF;
for(int i = ; i <= n + ; i++) {
if(a[i] != -) {
int l = , r = top;
while(l < r) {
int mid = (l + r + ) >> ;
if(p[mid] < a[i]) l = mid;
else r = mid - ;
}
fr[i] = frp[r];
if(r == top) {
p[++top] = a[i];
frp[top] = Node(i, );
}
else if(p[r + ] > a[i]) {
p[r + ] = a[i];
frp[r + ] = Node(i, );
}
}
else {
int p1 = top;
for(int j = ; j <= m; j++) {
while(p1 && p[p1] >= b[j]) {
p1--;
}
Node temp = frp[p1];
temp.b++;
if(p1 == top) {
p[++top] = b[j];
frp[top] = temp;
}
else if(p[p1 + ] > b[j]) {
p[p1 + ] = b[j];
frp[p1 + ] = temp;
}
}
}
} int now = frp[top].a, p1 = n, p2 = ;
while(now) {
if(fr[now].b) {
while(p1 > now) p1--;
while(b[p2] >= a[now]) p2++;
for(int i = ; i <= fr[now].b; i++) {
while(a[p1] != -) p1--;
a[p1] = b[p2];
vis[p2] = ;
p2++;
}
}
now = fr[now].a;
} p2 = ;
for(int i = ; i <= n; i++) {
if(a[i] == -) {
while(vis[p2]) p2++;
a[i] = b[p2];
p2++;
}
} for(int i = ; i <= n; i++) {
printf("%lld ", a[i]);
}
return ;
}
AC代码