洛谷P2215 [HAOI2007]上升序列 题解

题目链接：P2215 [HAOI2007]上升序列

题意：

对于一个给定的 $S=\{a_1,a_2,a_3,…,a_n\}$ , 若有 $P=\{a_{x_1},a_{x_2},a_{x_3},…,a_{x_m}\}$ , 满足 $(x_1<x_2<…<x_m)$ 且 $(a_{x_1}<a_{x_2}<…<a_{x_m})$ 。那么就称 $P$ 为 $S$ 的一个上升序列。如果有多个 $P$ 满足条件，那么我们想求字典序最小的那个。

任务：

给出 $S$ 序列，给出若干询问。对于第 $i$ 个询问，求出长度为 $L_i$ 的上升序列，如有多个，求出字典序最小的那个（即首先 $x_1$ 最小，如果不唯一，再看 $x_2$ 最小……），如果不存在长度为 $L_i$ 的上升序列，则打印 Impossible。

输入格式：

第一行一个 $N$，表示序列一共有 $N$ 个元素。

第二行 $N$ 个数，为 $a_1, a_2 , \cdots , a_n$。

第三行一个 $M$，表示询问次数。下面接 $M$ 行每行一个数 $L$，表示要询问长度为 $L$ 的上升序列。

输出格式：

对于每个询问，如果对应的序列存在，则输出，否则打印 Impossible。

数据范围：

$N \le 10000$，$M \le 1000$，保证数据随机。

假设某个询问的答案是 $a_i$ 开头

那下一步选 $a_{i+1}$ 会导致什么呢？

如果 $a_i,a_{i+1},a_{j_1},a_{j_2},\cdots.a_{j_{L-2}}$ 能构成一个长 $L$ 的上升子序列，那没问题

但是如果 $a_{i},a_{i+1}$ ，后面再怎么拼都拼不出长 $L$ 的上升子序列，我们就不能选

从这个过程中，我们可以发现，当前这个数是否添加到答案的上升序列

取决于它能否在之后的决策中构成一个符合答案长度的序列

设 $g_i$ 表示以 $i$ 开头能构成多长的上升子序列

其实就是后 $n-i+1$ 个数，能构成多长的不下降子序列

于是我们倒着跑一遍不下降子序列，得到 $g_i$ 。

对于询问，直接 $O(n)$ 跑就好啦

时间复杂度 $O(n \log n+nm)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N ((int)(1e4+15))

int n,Q,p,cnt,a[N],g[N],f[N];
int cmp(int x,int y){return a[x] > a[y];}
void solve(int len)
{
    int lst=-INF;
    for(int i=1; i<=n && len; i++)
        if(a[i] > lst && g[i] >= len)
            cout << (lst=a[i]) << " \n"[!(--len)];
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=1; i<=n; i++) cin >> a[i];
    f[cnt=1]=n; g[n]=1;
    for(int i=n-1; i; i--)
    {
        p=lower_bound(f+1,f+1+cnt,i,cmp)-f;
        f[p > cnt ? ++cnt : p]=i; g[i]=p;
    }
    for(cin >> Q; Q--; )
    {
        cin >> p;
        if(p <= cnt)solve(p);
        else cout << "Impossible\n";
    }
    return 0;
}