HDU6635

HDU6635

HDU6635-Nonsense Time(最长上升子序列+想法暴力)

题意

​ You a given a permutation p₁​,p₂​,…,p_n 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 p_ki will become available.

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

​ 大概题意是给出了一个n的置换，初始状态这些数之都处于冻结状态，每轮解冻一个数字，共n轮，求出每轮解冻数字之后，由解冻的数字组成的最长上升子序列长度。

​ 数据范围是5e4的，并且保证数据随机给出。

思路

​ 要是考虑每次插入一个数到特定位置，最长上升子序列长度就不好维护了，需要每次都重新求，显然复杂度会爆炸。但是可以将顺序倒过来考虑，将问题转化成每次从序列中删除一个数，维护最长上升子序列。这样的话，只要删去的数不在最长上升子序列里面，那么答案就不会发生变化，而要是把最长上升子序列里的数删掉了也没关系，我们重新求一遍最长上升子序列就好了，因为数据是随机给出的，所以求最长上升子序列的次数的期望是只有 n sqrt n n ​次的，因此这样的复杂度是足够我们通过这道题的，最后代码就是下面这样，每次判断删去的数在不在子序列里，在的话重新求一遍带路径记录的最长上升子序列，复杂度是 O ( n n l o g n ) O(nsqrt nlogn) O(nn ​logn)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
int n;
int a[50009],k[50009];
int s[50009];
int vis[50009];
int in[50009];
int ans[50009];
int fa[50009];
int main()
{ll T;scanf("%lld",&T);while (T --) {scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=n;i++)scanf("%d",&k[i]);for(int i=1;i<=n;i++)vis[i]=in[i]=ans[i]=fa[i]=0;int len=0;for(int i=1;i<=n;i++){if(len==0)s[len++]=i,fa[i]=0;else if(a[s[len-1]]<a[i]){fa[i]=s[len-1];s[len++]=i;}else {if(a[s[0]]>=a[i]){s[0]=i;fa[i]=0;continue;}int l=0,r=len-1;while(l<r){int mid=(l+r+1)/2;if(a[s[mid]]<a[i])l=mid;else r=mid-1;}s[l+1]=i;fa[i]=s[l];}}ans[n]=len;for(int i=s[len-1];i;i=fa[i])in[i]=1;for(int i=n;i>1;i--){vis[k[i]]=1;if(!in[k[i]])ans[i-1]=ans[i];else {for(int j=1;j<=n;j++)in[j]=0;len=0;for(int j=1;j<=n;j++){if(vis[j])continue;if(len==0)s[len++]=j,fa[j]=0;else if(a[s[len-1]]<a[j]){fa[j]=s[len-1];s[len++]=j;}else {if(a[s[0]]>=a[j]){s[0]=j;fa[i]=0;continue;}int l=0,r=len-1;while(l<r){int mid=(l+r+1)/2;if(a[s[mid]]<a[j])l=mid;else r=mid-1;}s[l+1]=j;fa[j]=s[l];}}ans[i-1]=len;for(int j=s[len-1];j;j=fa[j])in[j]=1;}}for(int i=1;i<=n;i++)printf("%d%c",ans[i],i==n?'n':' ');}
}