【ACM】HDU 6635 Nonsense Time 2019杭电多校第六场1002

【ACM】HDU 6635 Nonsense Time 2019杭电多校第六场1002

题目链接:

.php?pid=6635

Nonsense Time

Time Limit: 14000/14000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 918    Accepted Submission(s): 304

 

Problem Description

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.

Input

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.

Output

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.

Sample Input

1

5

2 5 3 1 4

1 4 5 3 2

Sample Output

1 1 2 3 3

题目大意：

给定一个长度为n的序列，每次解冻其中的一位，求每次解冻时的最长上升子序列的长度

思路：

这题不能从正面来思考，从正面思考就爆炸了。。。

先假设所有的位置都被解冻了，求一遍最长上升子序列，并把它保存起来，然后从后往前删，如果当前要删除的数字不在LIS中，表示这个数字对结果没有影响，结果就是当前LIS的长度。反之，要重新求一遍LIS。

这里主要是记录一下采用二分+贪心的方式求LIS怎么保存最长上升子序列中的数：

假设原数组为a，存放临时变量的数组为lis，如果直接求，lis数组里面存的不一定是最长上升子序列，我们在原来的基础上开一个pos数组记录当前元素a[i]在lis数组中的位置，遍历一遍a数组之后可以得到LIS的长度，最后我们在pos数组中取pos[i]=1,2,3,...,len(LIS)，这些a[i]就构成了一个最长上升子序列。

（感谢芳姨）

放上代码更加容易理解：

#include <bits/stdc++.h>
using namespace std;
const int maxn=50005;
int a[maxn],frozen[maxn];
int lis[maxn],pos[maxn],isfrozen[maxn];
int ans[maxn];
set <int> li;
int LIS(int n)
{li.clear();//记得清空，不清空会超时int maxl=1;for(int i=0; i<n; i++){if(isfrozen[i]==0){int mid=lower_bound(lis,lis+maxl,a[i])-lis;if(mid==maxl){pos[i]=maxl;lis[maxl++]=a[i];}else{lis[mid]=a[i];pos[i]=mid;}}}int k=maxl-1;for(int i=n-1; i>=0; i--){if(pos[i]==k&&isfrozen[i]==0&&k>0){li.insert(a[i]);k--;}}
//    for(set<int>::iterator iter=li.begin();iter!&#d();iter++)
//        cout<<"*"<<*iter<<endl;
//    for(int i=0;i<n;i++)
//        printf("%d ",pos[i]);
//    printf("n");return maxl-1;
}
int main()
{//freopen(&#","r",stdin);int t;scanf("%d",&t);while(t--){int n;scanf("%d",&n);for(int i=0; i<n; i++)scanf("%d",&a[i]);for(int i=0; i<n; i++){scanf("%d",&frozen[i]);frozen[i]--;}fill(isfrozen,isfrozen+n,0);int len=LIS(n);ans[n-1]=len,ans[0]=1;for(int i=n-1;i>=1;i--){isfrozen[frozen[i]]=1;unt(a[frozen[i]])==1){len=LIS(n);ans[i-1]=len;}elseans[i-1]=len;}//printf("%dn",len);for(int i=0;i<n;i++){if(i!=n-1)printf("%d ",ans[i]);elseprintf("%dn",ans[i]);}}return 0;
}