洛谷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;
}