插入的数是以递增的顺序插入的

这说明如果倒过来考虑，那么从最后一个插入的开始删除，不会对以某个数结尾的最长上升子序列产生影响

所以 先原序列求出来，输出即可

 

还原原序列的方法：

可以用平衡树，dfs序就是原序列

嫌麻烦，不想写，所以  树状数组

假设最后一个数是n，插入位置是y，

倒数第二个数是n-1，插入位置是x

那么y就是n的最终位置

如果y在x后面，那么x就是n-1的最终位置

如果y在x前面，那么x+1就是n-1的最终位置

所以 如果倒序插入每个数，

若数m的插入位置为p，

数m的最终位置就是当前序列 的 第p个空位

这可以二分+树状数组确定 数m的位置 

 

注意求LIS时，求出的f[i] 时 以i结尾的LIS

要求回答 序列的LIS，所以要跟f[i-1]取大

 

#include
     
      #include
      
       #include
       
        using namespace std;#define N 100001#define lowbit(x) x&-xint n;int p[N];int c[N];int a[N];int dp[N],m;int f[N];void read(int &x){    x=0; char c=getchar();    while(!isdigit(c)) c=getchar();    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }}    void add(int pos,int x){    while(pos<=n)    {        c[pos]+=x;        pos+=lowbit(pos);    }}int query(int x){    int sum=0;    while(x)    {        sum+=c[x];        x-=lowbit(x);    }    return sum;}int find(int x){    int l=1,r=n,mid,tmp;    while(l<=r)    {        mid=l+r>>1;        if(mid-query(mid)>=x) tmp=mid,r=mid-1;        else l=mid+1;    }    return tmp;}void init(){    read(n);    for(int i=1;i<=n;++i) read(p[i]);    int pos;    for(int i=n;i;--i)    {        pos=find(p[i]+1);        a[pos]=i;        add(pos,1);    }}void pre_LIS(){    dp[m=1]=a[1];    f[a[1]]=1;    int pos;    for(int i=2;i<=n;++i)    {        if(a[i]>dp[m])         {            dp[++m]=a[i];            f[a[i]]=m;        }            else        {            pos=lower_bound(dp+1,dp+m+1,a[i])-dp;            if(a[i]