Nonsense Time（LIS）

Nonsense Time（LIS）

题目描述
You a given a permutation p1,p2,…,pn of size n. Initially, all elements in p are frozen. There will be n stages that these elements will become available one by one. On stage i, the element pki will become available.

For each i, find the longest increasing subsequence among available elements after the first i stages.

输入
The first line of the input contains an integer T(1≤T≤3), denoting the number of test cases.
In each test case, there is one integer n(1≤n≤50000) in the first line, denoting the size of permutation.
In the second line, there are n distinct integers p1,p2,…,pn(1≤pi≤n), denoting the permutation.
In the third line, there are n distinct integers k1,k2,…,kn(1≤ki≤n), describing each stage.
It is guaranteed that p1,p2,…,pn and k1,k2,…,kn are generated randomly.

输出
For each test case, print a single line containing n integers, where the i-th integer denotes the length of the longest increasing subsequence among available elements after the first i stages.

样例输入
1
5
2 5 3 1 4
1 4 5 3 2

样例输出
1 1 2 3 3

思路
先用二分更新最大上升序列，标记上升关键点，再倒序依次冻结p_ki，若p_ki为关键点，则冻结后重新更新最大上升序列，即可得到答案。

代码实现

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=50005;
const int INF=0x3f3f3f;
int n,p[N],k[N];
int vis[N],lis[N],ans[N],tot[N],used[N];
int nl;
template<class T>
inline void read(T &ret)
{char c;ret=0;while((c=getchar())<'0' || c>'9');while(c>='0' && c<='9'){ret=ret*10+(c-'0');c=getchar();}
}
int Find()
{int len=0;for(int i=1;i<=n;i++){if(vis[p[i]]==-1) continue;int it=lower_bound(lis,lis+len,p[i])-lis;if(it==len){lis[len++]=p[i];tot[i]=len;}else{lis[it]=p[i];tot[i]=it+1;}}fill(used,used+N,0);int tmp=len;for(int i=n;i>=1;i--){if(vis[p[i]]==-1) continue;if(tot[i]==tmp){used[p[i]]=1;tmp--;}}return len;
}
int main()
{int T;read(T);while(T--){read(n);fill(vis,vis+1+n,0);for(int i=1;i<=n;++i) read(p[i]);for(int i=1;i<=n;++i) read(k[i]);ans[n]=Find();for(int i=n-1;i>=1;--i){vis[p[k[i+1]]]=-1;if(used[p[k[i+1]]]==0) ans[i]=ans[i+1];else ans[i]=Find();}for(int i=1;i<=n;++i){if(i>1) printf(" ");printf("%d",ans[i]);}puts("");}return 0;
}