首页 > 代码库 > HDOJ 题目3564 Another LIS(线段树单点更新,LIS)

HDOJ 题目3564 Another LIS(线段树单点更新,LIS)

Another LIS

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1291    Accepted Submission(s): 451


Problem Description
There is a sequence firstly empty. We begin to add number from 1 to N to the sequence, and every time we just add a single number to the sequence at a specific position. Now, we want to know length of the LIS (Longest Increasing Subsequence) after every time‘s add.
 

Input
An integer T (T <= 10), indicating there are T test cases.
For every test case, an integer N (1 <= N <= 100000) comes first, then there are N numbers, the k-th number Xk means that we add number k at position Xk (0 <= Xk <= k-1).See hint for more details.
 

Output
For the k-th test case, first output "Case #k:" in a separate line, then followed N lines indicating the answer. Output a blank line after every test case.
 

Sample Input
1 3 0 0 2
 

Sample Output
Case #1: 1 1 2
Hint
In the sample, we add three numbers to the sequence, and form three sequences. a. 1 b. 2 1 c. 2 1 3
 

Author
standy
 

Source
2010 ACM-ICPC Multi-University Training Contest(13)——Host by UESTC
 

Recommend
zhouzeyong   |   We have carefully selected several similar problems for you:  3572 2389 3584 3293 1255 
思路:就是从左插入找空位,从1~n用线段树记录他们的位置。然后再对他们的位置进行LIS就好
ac代码
#include<stdio.h>
#include<string.h>
#define max(a,b) (a>b?a:b)
int a[100010];
int node[100010<<2],d[100010],len,dp[100010];
void build(int l,int r,int tr)
{
	node[tr]=r-l+1;
	if(l==r)
		return;
	int mid=(l+r)>>1;
	build(l,mid,tr<<1);
	build(mid+1,r,tr<<1|1);
	node[tr]=node[tr<<1]+node[tr<<1|1];
}
int bin(int x)
{
	int l=1,r=len;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(x>dp[mid])
			l=mid+1;
		else
			r=mid-1;
	}
	return l;
}
void insert(int pos,int num,int l,int r,int tr)
{
	if(l==r)
	{
		d[num]=l;
		node[tr]=0;
		return;
	}
	int mid=(l+r)>>1;
	node[tr]--;
	if(pos<=node[tr<<1])
	{
		insert(pos,num,l,mid,tr<<1);
	}
	else
		insert(pos-node[tr<<1],num,mid+1,r,tr<<1|1);
}
int main()
{
	int t,c=0;
	scanf("%d",&t);
	while(t--)
	{
		int n;
		scanf("%d",&n);
		int i;
		for(i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			dp[i]=0;
		}
		build(1,n,1);
		for(i=n;i>0;i--)
		{
			insert(a[i]+1,i,1,n,1);
		}
		len=0;
		/*for(i=1;i<=n;i++)
		{
			printf("%d\n",d[i]);
		}*/
		printf("Case #%d:\n",++c);
		for(i=1;i<=n;i++)
		{
			int k=bin(d[i]);
			len=max(len,k);
			dp[k]=d[i];
			printf("%d\n",len);
		}
		printf("\n");
	}
}


 

HDOJ 题目3564 Another LIS(线段树单点更新,LIS)