[BZOJ 1046][HAOI 2007]上升序列(nlogn的LIS算法)

題目連結：http://www.lydsy.com:808/JudgeOnline/problem.php?id=1046

有人說這題是NOIP難度？表示懷疑，蒟蒻認為此題難度略大于NOIP。。。。

這個題的序列長度n<=1e4,如果用n^2的LIS做法肯定TLE，隻能用nlogn的算法，這種算法在http://www.slyar.com/blog/longest-ordered-subsequence.html中有詳細講解。

由于題目題意要求，我們需要求出以每個數字開頭的最長上升子序列長度，但是LIS最終得出的是每個數字結尾的最長子序列長度，是以我們需要把這個序列倒過來做，倒過來DP，求出在倒着的序列中，以每個數字結尾的最長下降子序列長度，這就相當于原序列中以每個數字開頭的最長上升子序列長度了。

然後再輸出答案即可。

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>

#define MAXN 100010

using namespace std;

int n,m,cnt,a[MAXN],f[MAXN],best[MAXN]; //f[i]=以第i個數字結尾的最長下降子序列長度，best[i]=長度為i的LIS的第i個元素,cnt=LIS長度

int BinarySearch(int x) //二分尋找大于x且最接近x的元素
{
    int lowerBound=1,upperBound=cnt,ans=0;
    while(lowerBound<=upperBound)
    {
        int mid=(lowerBound+upperBound)/2;
        if(best[mid]>x)
        {
            ans=mid;
            lowerBound=mid+1;
        }
        else upperBound=mid-1;
    }
    return ans;
}

void solve(int x) //輸出長度為x的上升子序列
{
    int last=0; //已經輸出的上升序列的最後一個數字
    for(int i=1;i<=n;i++)
        if(f[i]>=x&&a[i]>last)
        {
            printf("%d",a[i]);
            if(x!=1) printf(" "); //不是輸出最後一個數字，就要輸出空格，BZOJ好像不會過濾掉行末空格，是以要這樣做，防WA
            last=a[i];
            x--;
            if(!x) break;
        }
    printf("\n");
}

void preDP() //DP預處理
{
    for(int i=n;i>=1;i--)
    {
        int t=BinarySearch(a[i]);
        f[i]=t+1;
        cnt=max(cnt,t+1);
        if(best[t+1]<a[i])
            best[t+1]=a[i];
    }
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    preDP();
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        int len;
        scanf("%d",&len);
        if(len<=cnt)
            solve(len);
        else puts("Impossible");
    }
    return 0;
}