hdu3564 Another LIS

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

这题看了别人的题解，最后看懂了。题意是从1~n，一次插入位置，然后每插入一个数求出它的最长递增子序列（不连续）。可以用线段树先求出每个数所在的位置，可以从后往前，因为每次最后一个数的位置一定是固定的。然后就是二分法的lis了，这里如果继续用线段树求lis的话会超时的。

这里二分的lis之前一直看不懂，其实因为输入的数是一次增大的，所以每次只要记录这个数的位置，然后二分找到最接近但大于当前数的位置，然后替换掉找到的数。

这题我对二分又有了新的认识，二分模板不是固定的，而是根据题目意思决定最后返回的值是l还是r.

#include<iostream>

#include<stdio.h>

#include<string.h>

#include<math.h>

#include<vector>

#include<map>

#include<queue>

#include<stack>

#include<string>

#include<algorithm>

using namespace std;

#define maxn 100005

int a[maxn],ans[maxn],dp[maxn];

struct node{

    int l,r,n;

}b[4*maxn];

void build(int l,int r,int i)

{

    int mid;

    b[i].l=l;b[i].r=r;b[i].n=r-l+1;

    if(l==r)return;

    mid=(l+r)/2;

    build(l,mid,i*2);

    build(mid+1,r,i*2+1);

}

void update(int index,int m,int i)

{

    int mid;

    if(b[i].l==b[i].r){

        b[i].n=0;ans[m]=b[i].l;return;

    }

    if(b[i*2].n>=index) update(index,m,i*2);

    else update(index-b[i*2].n,m,i*2+1);

    b[i].n=b[i*2].n+b[i*2+1].n;

}

int find(int l,int r,int x)

{

    int mid;

    while(l<=r){

        mid=(l+r)/2;

        if(dp[mid]>x){

            r=mid-1;

        }

        else l=mid+1;

    }

    return r+1; //这里也可以是l,可以草稿纸上画一下

}

int main()

{

    int n,m,i,j,h,T,k,len; //len表示最长递增子序列

    scanf("%d",&T);

    for(h=1;h<=T;h++)

    {

        printf("Case #%d:\n",h);

        scanf("%d",&n);

        for(i=1;i<=n;i++){scanf("%d",&a[i]);dp[i]=0;}

        build(1,n,1);

        for(i=n;i>=1;i--){

            update(a[i]+1,i,1);

        }

        len=0;

        for(i=1;i<=n;i++){

            if(len==0){

                dp[++len]=ans[1];  //ans[]表示i所在的位置

                printf("%d\n",len);

                continue;

            }

            k=find(1,len,ans[i]);

            len=max(len,k); //不管这n个数排列顺序怎样，每一次的最长递增子序列一定是递增的，可以画一下。

            dp[k]=ans[i];  //dp[k]表示最长递增序列中的第k个数，用到了单调队列的思想

            printf("%d\n",len);

        }

        printf("\n");

    }

    return 0;

}

巴特西

hdu3564 Another LIS

最新文章

热门文章