独立集

独立集

给你一个n个数的全排列，问其中的最长上升子序列（LIS）长度，并求出哪些数一定在最长上升子序列中。N<=100,000 。

首先是如何在(O(nlog_2n))的时间内求出LIS。(d[k])表示前i个数中，长度为k的LIS末尾的最小数(k<=len)。显然，(d[k])是单调递增的。然后对于ai，二分查找正好大于ai的(d[k])，那么ai正好可以接在(d[k-1])后面。所以将(d[k])赋值为ai。其它的d都不用考虑，因为比k小的di，末尾的最小数肯定比ai小。比k大的di都大于ai，所以ai是接不上去的。如果ai比所有di都大，那么len++。最后的len就是LIS的长度。

那么如何求出一定在LIS中的数呢？如果一个数一定在LIS中，证明每一个LIS中都包含这个数，并且（在没有重复数字的前提下）这个数在所有LIS中所处的位置是相同的。因为如果有两个LIS，A，B，并且数x，在A中位置是i，在B中位置是j，假设i<j，那么B[j]之前的所有数都小于A[i]，那么把它们两个接在一起，就组成了一个更长的上升子序列，与A和B时LIS矛盾。所以，如果在原序列中，有两个数在LIS中的位置相同，证明这两个数可以互相替换，所以那两个数都不是一定在最长上升子序列中的。因此，我们只要求出原序列中每一个数在LIS中的编号，然后统计同一编号是否对应多个数就行了。

#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn=1e5+5;
int n, len, a[maxn], d[maxn];
int pos[maxn], pos2[maxn], cnt[maxn];
//pos[i]:a[i]在最长不下降子序列中的位置

int main(){
    scanf("%d", &n);
    for (int i=1; i<=n; ++i) scanf("%d", &a[i]);
    int k; d[++len]=a[1]; pos[1]=len;
    for (int i=2; i<=n; ++i){
        k=lower_bound(d+1, d+len+1, a[i])-d;
        if (k>len) len=k;
        d[k]=a[i]; pos[i]=k;
    }
    len=0; d[++len]=-a[n]; pos2[n]=len;
    for (int i=n-1; i>=1; --i){
        k=lower_bound(d+1, d+len+1, -a[i])-d;
        if (k>len) len=k;
        d[k]=-a[i]; pos2[i]=k;
    }
    for (int i=1; i<=n; ++i)
        if (pos[i]+pos2[i]>len) ++cnt[pos[i]];
    printf("%d
", len);
    for (int i=1; i<=n; ++i)
        if (pos[i]+pos2[i]>len&&cnt[pos[i]]==1) printf("%d ", i);

}