上升序列

题目描述：
对于一个给定的S={a1,a2,a3,…,an},若有P={ax1,ax2,ax3,…,axm},满足(x1 < x2 < … < xm)且（ ax1 < ax2 < … < axm)。那么就称P为S的一个上升序列。如果有多个P满足条件，那么我们想求字典序最小的那个。
任务给出S序列，给出若干询问。对于第i个询问，求出长度为Li的上升序列，如有多个，求出字典序最小的那个（即首先x1最小，如果不唯一，再看x2最小……），如果不存在长度为Li的上升序列，则打印Impossible.

输入：

第一行一个N，表示序列一共有N个元素第二行N个数，为a1,a2,…,an 第三行一个M，表示询问次数。
下面接M行每行一个数L，表示要询问长度为L的上升序列。

输出：

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

样例输入：

6

3 4 1 2 3 6

3

6

4

5

样例输出：

Impossible

1 2 3 6

Impossible

提示：

N<=10000,M<=1000

解题：

这道题，网上题解很多，可无奈大家都是高手，我是一点也看不懂，(我不是搞竞赛的，只想考考CSP，做做LeetCode，在全是大佬的世界里能够活下去就很满足了)倒着做最长下降子序列，还他妈用二分搜索来优化？什么东西啊！

后来经过一阵子的死磕，总算明白一点了。这篇博客用来记录我的感悟。

首先，这道题很容易超时，所以我们要自己手写一个快速读入函数：

（这个是板子，别管原理，记吧）

 1 int read()
 2 {
 3     int sum = 0;
 4     char a = ' ';
 5     while (a < '0' || a > '9') {
 6         a = getchar();
 7     }
 8     while (a >= '0' && a <= '9') {
 9         sum = 10 * sum + a - '0';
10         a = getchar();
11     }
12     return sum;
13 }

然后，我们要来一个二分搜索，这个二分搜索跟我学过的有一丁点儿不一样，也不知道是不是我的问题，总感觉这二分写得很诡异。我估计是因为我们要倒着来一遍最长下降子序列，然后通过二分搜索来找出最应该放的那个位置，所以改了一下。

 1 int search(int x, int l, int r)
 2 {
 3     int s = 0;
 4     while (l <= r) {
 5         int mid = (l + r) >> 1;
 6         if (dp[mid] > x) {
 7             s = mid;
 8             l = mid + 1;
 9         }
10         else {
11             r = mid - 1;
12         }
13     }
14     return s;
15 }

好了，接下来，两个准备的工具都已经准备好了，现在是我们的重头戏。我们来分析一下这道题，要求给定长度的上升序列，没有的话要输出不可能，怎么办呢？其实很简单，什么情况下会不可能？是不是如果我要求的这个长度甚至超过了这整个序列的最长上升序列长度，那就肯定不可能了？否则我只要取字典序最小的打印出来就可以了。诶，我们就有了大致思路，先拿我读进来的这个长度跟最大长度比较一下，符合条件，我再继续，否则直接输出不可能。

好了，那现在，如果长度是符合条件的，那我怎么处理呢？

在这里，我们先定义几个数组，a[]数组是读入进来的序列；dp[]数组是我们二分搜索的数组，这个数组里面保存的是我们最长下降子序列，也就是说，该数组的长度，就是最长下降子序列的长度；然后我们还有一个数组，f[]数组。这个数组是什么呢？有大用处，f[i]表示从i开始，一直到a[n]的最长上升子序列长度。注意这里是从i开始，不同于以往的从1到i.这个数组，是我在解决符合条件的情况的时候，用来打印出具体的序列的。

好，现在来看看怎么处理出f数组和dp数组。

 1 void work()
 2 {
 3     n = read();
 4     for (int i = 1; i <= n; ++i) {
 5         a[i] = read();
 6     }
 7     f[n] = 1;
 8     dp[1] = a[n];
 9     len = 1;
10     for (int i = n - 1; i >= 1; --i) {
11         int pos = search(a[i], 1, len);
12         if (pos == len) {
13             dp[++len] = a[i];
14         }
15         else if (a[i] > dp[pos + 1]) {
16             dp[pos + 1] = a[i];
17         }
18         f[i] = pos + 1;
19     }
20     m = read();
21     for (int i = 1; i <= m; ++i) {
22         l = read();
23         if (l > len) {
24             puts("Impossible");
25             continue;
26         }
27         solve(l);
28     }
29 }

这个work函数最后有一个solve函数，我们先不管它，先来看上面的代码。正常读入a数组后，我让f[n]=1.这是啥意思？这表示，从a数组最后一个元素开始，其最长上升子序列长度为1.这是显然的；然后，dp[1]=a[n].这就表示我倒着处理a的最长下降子序列，我从a的最后一个元素开始考虑。要注意这个值也是可能被替换掉的；最后一步，len=1.这表示目前最长下降子序列长度为1.准备工作就绪后，我们开始倒着处理a数组：我先而分出一个位置，在dp数组中找a数组的当前元素，当然一般是找不到的，除非有重复元素。那么这个时候，其实我找的就是可以插入的那个位置，因为我二分搜索搜索的是位置嘛，对吧。而这个二分搜索算法写得恰到好处，当我下一个要读入的元素比我现在已有的任何元素都小时，也就是说，我下一个要读入的数，a[i],比dp数组中任何元素都小的时候，那么这个时候我二分出来的位置，正好等于len.也就是正好会进入第一个if判断；而当我下一个读入的数据大时，我就会在dp数组中二分出来一个正好是第一个比它大的位置，（如果没有，那当然就是第0个位置）换句话说，我的dp是6,3,2,1.现在我读入的是4，那么我二分出来的位置，那个pos值，就会是6所在的位置，然后就会进入else if那个判断，pos+1,就会是3所在的位置。然后，这个时候，程序就会把dp数组2这个位置的值，由3更新为4，而且这个时候，len是不会更新的，而f[i]会变得更小。别问为什么，就有这么神奇。至于我是怎么知道的，手动模拟一遍就会了。（看这个想了好久都不会，还不如手动模拟一遍）

最后，是我们的solve函数。这个函数根据f数组来的，只要我读入的数比上一个小，并且长度还不比f[i]长，那就输出，打印出来。如果不懂，自己模拟一遍程序运行吧。

然后测试样例过了，异常兴奋地拿去oj上提交，啪，时间超限。

What the f..k?（哔————）

后来，加了一个东西，就过了。

嘿嘿嘿，跟爷斗？毛都没长齐呢！

#pragma GCC optimize ("O2")

喏，就是这个。

AC代码：

 1 #pragma GCC optimize ("O2")
 2 #include 
 3 #define N 10005
 4 int dp[N], a[N], f[N];
 5 int n, m, l, len;
 6 using namespace std;
 7 int read()
 8 {
 9     int sum = 0;
10     char a = ' ';
11     while (a < '0' || a > '9') {
12         a = getchar();
13     }
14     while (a >= '0' && a <= '9') {
15         sum = 10 * sum + a - '0';
16         a = getchar();
17     }
18     return sum;
19 }
20 int search(int x, int l, int r)
21 {
22     int s = 0;
23     while (l <= r) {
24         int mid = (l + r) >> 1;
25         if (dp[mid] > x) {
26             s = mid;
27             l = mid + 1;
28         }
29         else {
30             r = mid - 1;
31         }
32     }
33     return s;
34 }
35 void solve(int x)
36 {
37     int rest = -1;
38     for (int i = 1; i <= n; ++i) {
39         if (a[i] > rest && f[i] >= x) {
40             printf("%d", a[i]);
41             if (x != 1) {
42                 printf(" ");
43             }
44             rest = a[i];
45             x--;
46             if (!x) {
47                 break;
48             }
49         }
50     }
51     printf("\n");
52 }
53 void work()
54 {
55     n = read();
56     for (int i = 1; i <= n; ++i) {
57         a[i] = read();
58     }
59     f[n] = 1;
60     dp[1] = a[n];
61     len = 1;
62     for (int i = n - 1; i >= 1; --i) {
63         int pos = search(a[i], 1, len);
64         if (pos == len) {
65             dp[++len] = a[i];
66         }
67         else if (a[i] > dp[pos + 1]) {
68             dp[pos + 1] = a[i];
69         }
70         f[i] = pos + 1;
71     }
72     m = read();
73     for (int i = 1; i <= m; ++i) {
74         l = read();
75         if (l > len) {
76             puts("Impossible");
77             continue;
78         }
79         solve(l);
80     }
81 }
82 int main()
83 {
84     work();
85     return 0;
86 }