2019hdu暑假多校训练赛第六场1002 Nonsense Time hdu6635（LIS）

2019hdu暑假多校训练赛第六场1002 Nonsense Time hdu6635（LIS）

题目链接：.php?pid=6635

题意：给出大小为n的a数组（每一个a[i]都不相同），再给出一个大小为n的b数组，b数组的中的b[i]代表a数组中下标为b[i]的数字可以用，对于每次输入b[i后]求一个新的最长上升子序列的长度，此题数据是随机的。

数据范围：1≤T≤3，1≤n≤50000，1≤ai≤n,1<=bi<=n

思路：因为数据是随机的，有一个结论是最长上升子序列的长度为sqrt（n），那么此题我们可以考虑时光倒流，从后往往前算，每次都是冻结一个数字不可以用，那么起初我们只需要计算一遍LIS，对于冻结某个数是看一看是否是之前的LIS中的一个数，如果是的话就需要重新求一遍LIS，否则无影响。对于这道题，我的队友想出了一个比题解更容易懂的记录LIS都是那些数的方法，只需要多一个pre数组，数组中记录的是在LIS中它前面那一项的数是谁，那么对于LIS的最后一项一直访问pre就可以得到完整的LIS。本题不用离散化，不过写了离散化可以让这个思路的适用范围更广一点。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e4+10;
int n,t,cnt,a[N],ice[N],G[N],pre[N],ans[N],xx[N];
bool vis[N];
inline void LIS(){cnt=G[0]=0;for(int i=1; i<=n; i++){vis[i]=0;if(a[i]==-1)continue;if(a[i]>G[cnt]){G[++cnt]=a[i];pre[a[i]]=G[cnt-1];}else{int pos=lower_bound(G,G+cnt+1,a[i])-G;pre[a[i]]=G[pos-1];G[pos]=a[i];}}///标记上当前的上升子序列是谁for(int i=G[cnt],j=cnt; j; j--,i=pre[i])vis[i]=1;
}
int main(){scanf("%d",&t);while(t--){scanf("%d",&n);for(int i=1; i<=n; i++)scanf("%d",&a[i]),xx[i]=a[i];sort(xx+1,xx+n+1);///离散化for(int i=1;i<=n;i++)a[i]=lower_bound(xx+1,xx+n+1,a[i])-xx;for(int i=1; i<=n; i++)scanf("%d",&ice[i]);LIS();ans[n]=cnt;for(int i=n; i>1; i--){if(vis[a[ice[i]]]==1){a[ice[i]]=-1;LIS();}a[ice[i]]=-1;ans[i-1]=cnt;}for(int i=1;i<=n;i++)printf("%d%c",ans[i]," n"[i==n]);}return 0;
}