https://www.lydsy.com/JudgeOnline/problem.php?id=3173
插入的数是以递增的顺序插入的
这说明如果倒过来考虑，那么从最后一个插入的开始删除，不会对以某个数结尾的最长上升子序列产生影响
所以 先原序列求出来，输出即可
还原原序列的方法：
可以用平衡树，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<cstdio>
#include<iostream>
#include<algorithm> using namespace std; #define N 100001 #define lowbit(x) x&-x int n;
int p[N]; int c[N]; int a[N];
int dp[N],m;
int f[N]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} void add(int pos,int x)
{
while(pos<=n)
{
c[pos]+=x;
pos+=lowbit(pos);
}
} int query(int x)
{
int sum=;
while(x)
{
sum+=c[x];
x-=lowbit(x);
}
return sum;
} int find(int x)
{
int l=,r=n,mid,tmp;
while(l<=r)
{
mid=l+r>>;
if(mid-query(mid)>=x) tmp=mid,r=mid-;
else l=mid+;
}
return tmp;
} void init()
{
read(n);
for(int i=;i<=n;++i) read(p[i]);
int pos;
for(int i=n;i;--i)
{
pos=find(p[i]+);
a[pos]=i;
add(pos,);
}
} void pre_LIS()
{
dp[m=]=a[];
f[a[]]=;
int pos;
for(int i=;i<=n;++i)
{
if(a[i]>dp[m])
{
dp[++m]=a[i];
f[a[i]]=m;
}
else
{
pos=lower_bound(dp+,dp+m+,a[i])-dp;
if(a[i]<dp[pos]) dp[pos]=a[i];
f[a[i]]=pos;
}
}
} void solve()
{
int now=;
for(int i=;i<=n;++i)
{
now=max(now,f[i]);
printf("%d\n",now);
}
} int main()
{
init();
pre_LIS();
solve();
}