最长单调上升子序列
#include#include #include #include using namespace std;int f[1000000];int z[1000000];int lowbit(int x){ return x&-x;}int big;inline int ask(int x){ int r=0; for(int i=x;i>0;i-=lowbit(i)) r=max(r,f[i]); return r;}inline void add(int x,int v){ for(int i=x;i<=big;i+=lowbit(i)) f[i]=max(f[i],v);}inline int que(int x）{ int r=0; for(int i=x;i<=big;i+=lowbit(i)) r=max(r,f[i]); return r;}inline void psh(int x,int v){ for(int i=x;i>0;i-=lowbit(i)) f[i]=max(f[i],v);}int tot;int a[1000000];int ans;int main(){ tot=1; while(scanf("%d",&a[tot])!=EOF) { big=max(big,a[tot]); z[tot]=a[tot]; tot++; } tot--; for(int i=1;i<=tot;i++) { int x=ask(a[i])+1; ans=max(ans,x); add(a[i]+1,x); } memset(f,0,sizeof(f)); int num=0; for(int i=1;i<=tot;i++) { int x=que(a[i])+1; num=max(num,x); psh(a[i],x); } printf("%d\n%d",num,ans); return 0;}