Nonsense Time（LIS元素集合求解）

本文主要是介绍Nonsense Time（LIS元素集合求解），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题： http://acm.hdu.edu.cn/showproblem.php?pid=6635

题意：

给出一个排序，当前所有数字不能使用。给出可以使用的顺序，求每次加入新的可以使用的数字后的最长上升子序列长度。

解析：

我们考虑从后往前找，把加入改为删除。因为数据随机，所以删除序列内元素的期望为 $O (l o g N)$ 。所以我们可以暴力去做，如果删除的元素在序列里面就重新做。

维护栈内元素的过程大致如下：
在这里插入图片描述
从最后一个扩栈的元素往回回溯就是答案。

代码：

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
const int maxn=5e4+9;
int a[maxn],p[maxn];
bool cut[maxn];
bool in[maxn];int ar[maxn],top;
int pre[maxn];int deal(int n){memset(in,0,sizeof in);top=0;int En;for(int i=1;i<=n;i++){if(cut[a[i]])continue;if(top==0)ar[top=1]=a[i],pre[a[i]]=0,En=a[i];else if(a[i]>ar[top]){ar[++top]=a[i];pre[a[i]]=ar[top-1];En=a[i];}else{int pos=lower_bound(ar+1,ar+1+top,a[i])-ar;ar[pos]=a[i];pre[a[i]]=ar[pos-1];}}while(En){in[En]=1;En=pre[En];}return top;
}int main(){int t;scanf("%d",&t);while(t--){memset(cut,0,sizeof cut);int n;scanf("%d",&n);rep(i,1,n){scanf("%d",a+i);}rep(i,1,n){scanf("%d",p+i);}int len=deal(n);vector<int>V(n+1);V[n]=len;per(i,n,2){cut[a[p[i]]]=1;if(in[a[p[i]]]){len=deal(n);}V[i-1]=len;}rep(i,1,n){printf("%d%c",V[i]," \n"[i==n]);}}
}