题解 CF568E 【Longest Increasing Subsequence】
starseven
2020-06-12 14:48:31
[CF通道](http://codeforces.com/problemset/problem/568/E)
[我的博文链接](https://www.cnblogs.com/starseven/p/13099381.html)
[luogu链接](https://www.luogu.com.cn/problem/CF568E)
-------
# 大致题意
给你一个长度为n的序列，这其中可能有-1，代表着空位
然后给你m个数，代表空位可选的m个数
然后叫你补全序列（每个$b[i]$只能用一遍），是补全后得到的序列LIS（严格）最大
输入格式:
$n$
$a_1\;a_2\;a_3\cdots\;a_n$
$m$
$b_1\;b_2\;b_3\cdots\;b_m$
------
# 思路分析
因为这道题是叫我们求LIS的构造方案，我们(~~理所应当~~)应该想到LIS的求的方法。
1. 方法1：循环枚举法（$n^2$）
这个方法是利用双重$for$循环，然后进行LIS的判断
```cpp
//LIS[i]代表的是以i为终点的LIS的最大长度
for(register int i=1;i<=n;i++)
for(register int j=0;j<i;j++)
if(a[i]>a[j]) dp[i]=max(dp[i],dp[j]+1);
```
2. 方法2：利用辅助数组$f[i]$进行LIS($n\times logn$)
$f[x]$代表的是长度为x的LIS的末尾项最小是多少，而我们每一次遍历到$i$时，我们都可以进行二分查找，找到小于$a[i]$的最大的f[x],然后赋值$f[x+1]=a[i]$
```cpp
//f[i]意义同上
//ans代表的是最长上升子序列
memset(f,0x3f3f3f3f3f,sizeof(f));
for(register int i=1;i<=n;i++){
int j=lower_bound(f+1,f+1+n,a[i])-f-1;
f[j+1]=a[i];
ans=max(ans,j+1);
}
```
-----------------
从复杂度讲
$$ n \leq 10^5 $$
还是从是否有空位讲
我们都应该选择从第二个方法入手。
显而易见，我们应该把空位和数字分开处理。
- 数字
对于数字来说，我们就按照上面的LIS一样处理就好了
- 空位
对于空位来说，我们应该在这个位置上枚举每一个$b[i]$，然后分别像数字一样用LIS。
----------
感觉上是不是弄好了，但是有一点值得注意的是，答案不是叫我们输出可能得到的最大LIS的长度，而是叫我们输出修改后的序列，使这个序列里面有可能长度最大的LIS，所以我们还有两个问题亟需解决。
1. 题目中要求每个$b[i]$只能用一遍
2. 如何输出我们求到的序列
-----
$ \text{\red{{Solution}} :}$
1. 关于只能用一遍
因为如果我们在两个不同的空位用上相同的位置，这两个位置之间没有办法做出贡献（因为要求的是严格），所以即使我们这两个点都是相同的，那么对于前面的序列，贡献都一样，而互相没有贡献，所以这个限制我们可以忽略。
2. 关于输出
我们要输出这个序列，如果是正序枚举然后挨个挨个向后推的话显然是没法的。
## 原因：
因为你用LIS求出来的永远都只是以这个点为**终点**可以构造出来的最长LIS，所以你遍历到这个点可以保证在这个点之前可以构造LIS，可是如果你从前往后遍历的话，你根本不知道你现在构造出来的序列是不是你要求的最终序列，所以只能从后往前构造，而不能从前往后构造。
----
所以我们选择从后往前构造，现在问题又来了，请问你遍历到一个点后，你打算跳到哪个点呢？
这时候我们应该增加两个辅助数组，一个是$g[i]$代表的是以i为结束点的LIS长度是多少，一个$h[i]$代表的是以i为结束点的LIS的上一个点是多少。
而且我们必须保证i不为空位
为什么呢？
因为我们对于空位的处理方法是枚举这m个数，然后挨个挨个去更新，那么最坏情况下这个位置上有m个不同的LIS，那么违反了我们两个数组的定义，所以我们不能算上空格。
所以：
1. 位置不是空位
看$h[i]$就好了
2. 位置是空位
那么就先找有没有不是空位的数可以构造出剩下的LIS，不然的话就用最近的空格。
（因为我们保证了每个数我们都清楚以他为终点的LIS的最大长度，所以我们可以先找确定的点，这样的话我们就省下了一个填补的数，而如果非得用空格的话，那就选最近的空格，这也是一个贪心的思想）
---------
# 基于上面的思想，我们就可以打代码了（具体细节还得看代码）
$$ \blue{Talk\;is\;cheap,show\;the\;code\;!} $$
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
#define ri register int
#define Starsseven main
using namespace std;
const int N=1e5+20;
const int inf=999999999;
int a[N],b[N];
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;
}
int n,m,ans[N];
int Lis_minn[N]/*这个数组[i]表示的是LIS长为i时结尾最小的数*/,Lis_this[N]/*表示的是以i结尾(i不是空位)的LIS长度*/;
int Lis_last[N]/*这个数组表示的是长度为i的LIS的结尾最小值位置在哪里*/,Lis_before[N]/*表的是以i(i不是空位)为结尾的LIS的上一项*/;
bool vis[N];
void Find(int i,int h,int &x){
int j=lower_bound(b+1,b+1+m,h)-b-1;
vis[j]=1;x=ans[i]=b[j];
}
//Find(Lis_before[j],a[j],x)
int main(void){
n=read();//表示有n个数构成的序列
for(ri i=1;i<=n;i++) a[i]=read();//读入a[i]
n++;a[n]=inf;
m=read();//表示有m个可选的数
for(ri i=1;i<=m;i++) b[i]=read();//表示这m个数的大小
sort(b+1,b+1+m);//将b[]从小到大排序，因为我们之后要用到的是二分出最小的b[i]可以替换
for(ri i=1;i<=n;i++) Lis_minn[i]=inf;//先初始化minn数组
//int Lis_minn[N]/*这个数组[i]表示的是LIS长为i时结尾最小的数*/,Lis_this[N]/*表示的是以i结尾(i不是空位)的LIS长度*/;
//int Lis_last[N]/*这个数组表示的是长度为i的LIS的结尾最小值位置在哪里*/,Lis_before[N]/*表的是以i(i不是空位)为结尾的LIS的上一项*/;
for(ri i=1;i<=n;i++)/*从前往后枚举a[i]*/{
if(a[i]!=-1){//表示这个数不是空位
int j=lower_bound(Lis_minn+1,Lis_minn+1+n,a[i])-Lis_minn-1;//这个表示的是找到可以更新得到的数组
/*因为lower_bound求的是Lis_minn中小于a[i]的最大值，这样就可以保证:
在j之后的数a[i]更新不了
而在j之前的数，因为a[i]>Lis_minn[j],如果更新j-1则绝对不是"最小值"*/
Lis_minn[j+1]=a[i];Lis_this[i]=j+1;
Lis_last[j+1]=i; Lis_before[i]=Lis_last[j];
}
else{//表示这就是空位
for(ri j=m,x=n;j;j--){
while(Lis_minn[x]>=b[j]) --x;//找到b[j]可以更新的长度为x-1的数，为什么不更新前面的和后面的同理同上
Lis_minn[x+1]=b[j];
Lis_last[x+1]=i;
}
}
}
//下面是输出答案
ri i=Lis_this[n],j=n,x=a[j];
while(i--){
//int Lis_minn[N]/*这个数组[i]表示的是LIS长为i时结尾最小的数*/,Lis_this[N]/*表示的是以i结尾(i不是空位)的LIS长度*/;
//int Lis_last[N]/*这个数组表示的是长度为i的LIS的结尾最小值位置在哪里*/,Lis_before[N]/*表的是以i(i不是空位)为结尾的LIS的上一项*/;
if(a[j]!=-1){
if(a[Lis_before[j]]==-1) Find(Lis_before[j],a[j],x);
else x=a[Lis_before[j]];
j=Lis_before[j];
}
else{
bool Judge=false;
for(ri s=j-1;s;s--)
if(a[s]!=-1&&Lis_this[s]==i&&a[s]<x){
x=a[j=s],Judge=1;break;
}
if(Judge) continue;
for(ri s=j-1;s;s--){
if(a[s]==-1){
Find(s,x,x),j=s;
break;
}
}
}
}
for(ri i=1,j=1;i<=n;i++){
if(a[i]==-1){
if(ans[i]) continue;
while(vis[j]) j++;
vis[j]=1,ans[i]=b[j];
}
else ans[i]=a[i];
}
for(ri i=1;i<n;i++) printf("%d ",ans[i]);
return 0;
}
```