HDOJ 题目3564 Another LIS（线段树单点更新，LIS）

时间：2023-03-09 14:18:59
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
Recommend
思路：就是从左插入找空位，从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");

	}

}


相关文章