题目描述

有一天，一个名叫顺旺基的程序员从石头里诞生了。又有一天，他学会了冒泡排序和独立集。在一个图里，独立集就是一个点集，满足任意两个点之间没有边。于是他就想把这两个东西结合在一起。众所周知，独立集是需要一个图的。那么顺旺基同学创造了一个算法，从冒泡排序中产生一个无向图。  这个算法不标准的伪代码如下： 
procedure bubblesortgraph(n, a[]) ： 
                     /*输入：点数n，1到n的全排列a。 
                       输出：一个点数为n的无向图G。*/ 
                  创建一个有n个点，0条边的无向图G。 
                   repeat 
                        swapped = false 
                        for i 从 1 到 n-1 ： 
                              if a[i] > a[i + 1] ： 
                                    在G中连接点a[i]和点a[i + 1] 
                                    交换a[i]和a[i + 1] 
                                   swapped = true 
                   until not swapped 
                   输出图G。 
                    //结束。 

那么我们要算出这个无向图G最大独立集的大小。但是事情不止于此。顺旺基同学有时候心情会不爽，这个时候他就会要求你再回答多一个问题：最大独立集可能不是唯一的，但有些点是一定要选的，问哪些点一定会在最大独立集里。今天恰好他不爽，被他问到的同学就求助于你了。

思路

 因为题目中是将i > j 的边连起来，所以只用将数据跑一遍最长上升子序列就可以了

然后第二问就可以倒着跑一边最长下降子序列，如果f[i] + fl[i] = max + 1 那么就肯定是一个唯一的，也就是一个答案

还有如果f中有多个相同的话那这个肯定不会是一个答案

#include 
#include 
using namespace std;
#define maxn 100001
#define INF 0x7f7f7f7f
int a[maxn], f[maxn], fl[maxn], d[maxn], flaj[maxn];
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    int last = 0;
    for (int i = 1; i <= n; i++)
    {
        int t = lower_bound(d + 1, d + last + 1, a[i]) - d;
        if (last < t) last = t;
        f[i] = t;
        d[t] = a[i];
    }
    printf("%d\n", last);
    last = 0;
    for (int i = n; i >= 1; i--)
    {
        int t = lower_bound(d + 1, d + last + 1, -a[i]) - d;
        if (last < t) last = t;
        fl[i] = t;
        d[t] = -a[i];
    }
    for (int i = 1; i <= n; i++)
        if (f[i] + fl[i] == last + 1)
            flaj[f[i]]++;
    for (int i = 1; i <= n; i++)
        if (flaj[f[i]] == 1 && f[i] + fl[i] == last + 1) 
            printf("%d ", i);
}