就是求最长不下降子序列
#include<bits/stdc++.h>
const int maxn=100001;
int big[maxn<<2];
inline const void update(int p)
{
big[p]=std::max(big[p<<1],big[p<<1|1]);
}
inline const void modify(int p,int l,int r,int pos,int k)
{
if(l==r&&r==pos){big[p]=k;return ;}
int mid=(l+r)>>1;
if(mid>=pos)modify(p<<1,l,mid,pos,k);
if(mid+1<=pos)modify(p<<1|1,mid+1,r,pos,k);
update(p);
}
inline const int query(int p,int l,int r,int rr)
{
if(r<=rr)return big[p];
int mid=(l+r)>>1,ans=-1;
ans=query(p<<1,l,mid,rr);
if(mid+1<=rr)ans=std::max(ans,query(p<<1|1,mid+1,r,rr));
return ans;
}
int main()
{
memset(big,0,sizeof(big));
int n,a[maxn],f[maxn],ans=-1;
std::cin>>n;
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
{
f[i]=0;
f[i]=query(1,0,n,a[i])+1;
modify(1,0,n,a[i],f[i]);
ans=std::max(ans,f[i]);
}
std::cout<<ans;
return 0;
}