0%

CF568E工作报告

摘要:魔改版lis问题

CF568E Longest Increasing Subsequence

题面

题目分析

给定一个长度为n的序列a,其中有一些空缺,要求用m个数的数列b来补全a并最大化a的lis.

先对b排序使其满足单调性.

设出一些状态:i位不为空缺,l[i]表示$(1,i)$中包含i的最长lis的长度,p[i]表示lis中上一项的位置.

f[i]表示长度为i的lis中最后一项的最小值,g[i]则是这个最小值所在的位置.

然后考虑每一个位置,如果这个位置不是空缺的,那么直接按照$O(nlogn)$版的lis更新即可,依次更新l[i]=pla+1,g[pla+1]=i,p[i]=g[pla],f[pla]=a[i].

如果这个位置是空缺的,因为f和b都有单调性,我们考虑使用双指针遍历出应该填上的数,然后更新f和g.

然后考虑还原出补全的序列,显然需要倒序还原.

设现在还原出了lis的第i位,这一位的数字是now,在原序列上第j位.

如果一个位置不为空,直接用p[i]找到上一项位置即可.

如果一个位置为空,那么我们需要找到在他前面不为空的位置k中$l[k] = i - 1$且$a[k ] < now$的位置,如果没有找到该位置,就说明他前面的位置是一个空缺,找出b中小于now且最大的数即可.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include "iostream"
#include "cstdio"
#include "cstring"
#include "cmath"
#include "cstdlib"
#include "cctype"
#include "algorithm"
#include "set"
#include "queue"
#include "map"
#include "stack"
#include "vector"
#define lxl int
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%lld\n",x)
const lxl maxn=100010;
inline lxl read()
{
char c=getchar();
lxl f=1,x=0;
for(;!isdigit(c);c=getchar())(c=='-')&&(f=-1);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
return f*x;
}
lxl n,m,now;
lxl a[maxn],b[maxn],l[maxn],g[maxn],f[maxn],p[maxn],ans[maxn];
bool vis[maxn];
inline lxl work(lxl k,lxl val)
{
lxl o=std::lower_bound(b+1,b+1+m,val)-b-1;
vis[o]=true,ans[k]=b[o];
return b[o];
}
inline void go()
{
for(R int i(1);i<=n;++i)
{
if(a[i]!=-1)
{
lxl pla=std::lower_bound(f+1,f+1+n,a[i])-f-1;
f[pla+1]=a[i],l[i]=pla+1,p[i]=g[pla],g[pla+1]=i;
}
else
for(R int t(n),y(m);y;--y)
{
while(f[t]>=b[y])--t;
f[t+1]=b[y],g[t+1]=i;
}
}
}
inline void re()
{
int i=l[n],j=n;
while(i--)
{
if(a[j]!=-1)
{
if(a[p[j]]==-1)now=work(p[j],a[j]);
else now=a[p[j]];
j=p[j];
}
else
{
bool falg=false;
for(R int k(j-1);k;--k)
if(a[k]!=-1&&l[k]==i&&a[k]<now)
{
j=k;
now=a[j];
falg=true;
break;
}
if(falg)continue;
for(R int k(j-1);k;--k)
if(a[k]==-1)
{
now=work(k,now),j=k;
break;
}
}
}
}
int main(void)
{
// freopen("data.txt","r",stdin);
// freopen("my.out","w",stdout);
n=read();
for(R int i(1);i<=n;++i)a[i]=read(),f[i]=INF;
a[++n]=f[n]=INF;
m=read();
for(R int i(1);i<=m;++i)b[i]=read();
std::sort(b+1,b+1+m);
go();
now=a[n];
re();
for(R int i(1),j(1);i<=n;++i)
if(a[i]==-1)
{
if(ans[i])continue;
while(vis[j])++j;
vis[j]=true,ans[i]=b[j];
}
else ans[i]=a[i];
for(R int i(1);i<n;++i)printf("%d ",ans[i]);
printf("\n");
return 0;
}