2019 hdu 多校6 Nonsense Time（lis）

2019 hdu 多校6 Nonsense Time（lis）

链接

题意：

有n个不重复数字（范围[1，n]），数字按照顺序出现，求第i个数字出现时的lis长度。

题解：

反过来考虑删数字，先对整个数组做一个lis，并且找到一种方案。然后删数字的时候考虑一下这个数字在不在找到的lis序列中。若不在，就没啥关系，若在的话就再次nlogn做lis并找出新的lis序列。至于为什么只需要做大约 n sqrt n n ​次就看官方题解的解释：因为数据随机，因此 LIS 的期望长度是 O n Osqrt n On ​，删除的 x 位于 LIS 中的概率是 1 / n 1/sqrt n 1/n ​，也就是说期望删除 n sqrt n n ​ 个数才会修改 LIS，那么 LIS 变化的次数不会很多。

如何找到lis序列：nlogn的lis做法中要二分找到第一个大于等于当前数的数，那么前面一位就肯定小于自己了，把前面那个数当成自己的前驱。整个lis做完后，把最后一个数拿出来，不断找前驱就可以把整个lis序列找出来了。

参考代码：

#include <bits/stdc++.h>
using namespace std;const int N=50005;
const int INF=1e9+7;
int a[N],b[N];
bool vis[N],ff[N];
int dp[N],fa[N];
int n,sz;
int ans[N];void lis(){sz=0;dp[0]=-1;for(int i=1;i<=n+1;i++)dp[i]=INF;for(int i=1;i<=n;i++){ff[a[i]]= false;if(vis[a[i]])continue;int xb=lower_bound(dp+1,dp+n+1,a[i])-dp-1;if(!sz){fa[a[i]]=-1;}else{fa[a[i]]=dp[xb];}dp[xb+1]=a[i];sz=lower_bound(dp+1,dp+n+1,INF)-dp-1;}int u=dp[sz];while (u!=-1){ff[u]=true;u=fa[u];}
}int main(){int t;scanf("%d",&t);for(int ca=1;ca<=t;ca++){memset(vis,0, sizeof(vis));scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}for(int i=1;i<=n;i++){scanf("%d",&b[i]);}lis();ans[n]=sz;for(int i=n;i>=2;i--){vis[a[b[i]]]= true;if(ff[a[b[i]]]){lis();}ans[i-1]=sz;}for(int i=1;i<=n;i++){printf("%d%c",ans[i],i==n?'n':' ');}}return 0;
}