BZOJ 1046 [HAOI2007]上升序列

#include <cstdio>
#include <string>
#include <algorithm>

const int N = 10005;
int f[N], d[N], a[N], len, n;

int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (!isdigit(c)) {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (isdigit(c)) {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
int max(int x, int y) {
    if (x >= y) return x; return y;
}
int find(int x) {
    int l = 1, r = len, res = 0;
    while (l <= r) {
        int mid = l + (r - l >> 1);
        if (d[mid] > x) res = mid, l = mid + 1;
        else r = mid - 1;
    }
    return res;
}
void fly(int x) {
    int last = 0;
    for (int i = 1; i <= n; ++i) {
        if (f[i] >= x && a[i] > last) {
            printf("%d ", a[i]);
            last = a[i], --x;
            if (!x) break;
        }
    }
    puts("");
}
int main() {
    n = read();
    for (int i = 1; i <= n; ++i) a[i] = read();
    for (int i = n; i; --i) {
        int t = find(a[i]);
        f[i] = t + 1, len = max(len, f[i]);
        if (d[t+1] < a[i]) d[t+1] = a[i];
    }
    int m = read();
    while (m--) {
        int x = read();
        if (x <= len) fly(x);
        else puts("Impossible");
    }
    return 0;
}