【BZOJ】1046 : [HAOI2007]上升序列

时间：2024-12-21 15:06:14

1046: [HAOI2007]上升序列

题意:给定S={a1,a2,a3,…,an}问是否存在P={ax1,ax2,ax3,…,axm},满足(x1 < x2 < … < xm)且（ ax1 < ax2 < … < axm),若存在多组符合长度为m的递增子序列，则输出以序号字典序最小的；并非是数值

Sample Input

6
3 4 1 2 3 6
3
6
4
5

Sample Output

Impossible
1 2 3 6
Impossible
数据范围 N<=10000 ，M<=1000
思路:数据范围较大，且查询次数较多，应该要使用LIS的nlogn算法预处理出以每个位置开始的最长上升序列的长度len[];之后就可以从前往后直接看是否len[]>index，同时不能忘了还要是递增的；这样就自然要想到后面处理的是前面的pos，即从后往前处理，但是要变成最长下降子序列。
#include<iostream>

#include<cstdio>

#include<cstring>

#include<string.h>

#include<algorithm>

#include<map>

#include<queue>

#include<vector>

#include<cmath>

#include<stdlib.h>

#include<time.h>

using namespace std;

#define rep0(i,l,r) for(int i = (l);i < (r);i++)

#define rep1(i,l,r) for(int i = (l);i <= (r);i++)

#define rep_0(i,r,l) for(int i = (r);i > (l);i--)

#define rep_1(i,r,l) for(int i = (r);i >= (l);i--)

#define MS0(a) memset(a,0,sizeof(a))

#define MS1(a) memset(a,-1,sizeof(a))

#define inf 0x3f3f3f3f

const int MAXN = ;

int a[MAXN];

int stk[MAXN],len[MAXN];

int main()

{

    int n,Q,top = ;

    scanf("%d",&n);

    rep0(i,,n) scanf("%d",a + i),stk[i] = -inf;

    stk[] = inf;

    rep_1(i,n-,){// **

        int l = ,r = top,ret = top;

        while(l <= r){

            int mid = (l+r)>>;

            if(stk[mid] > a[i]) ret = mid,l = mid + ;

            else r = mid - ;

        }

        top = max(top,++ret);//存放在ret + 1处；

        stk[ret] = max(stk[ret],a[i]);//长度为ret的最大的值;即下降的贪心处理

        len[i] = ret;//从后往前下降，即该点的最长上升序列的长度；

    }

    //cout<<top<<endl;

    scanf("%d",&Q);

    int index;

    rep0(i,,Q){

        scanf("%d",&index);

        if(index > top) puts("Impossible");

        else{

            for(int i = ,post = -inf;index && i < n;i++){

                if(len[i] >= index && a[i] > post) // ***a[i] > post

                     printf("%d%c",a[i],--index?' ':'\n'),post = a[i];

            }

        }

    }

    return ;

}

相关文章