值域上建立线段树,区间查询,单点改
#include <iostream> #include<queue> #include <cstring> #define IOS std::ios::sync_with_stdio(0) using namespace std; const int N = 1e5, M =1e5; #define k1 k<<1 #define k2 k<<1|1 int n,f[N],a[N]; int mx[M<<2],L=0 ; void up(int k){ mx[k] =max(mx[k1],mx[k2]) ; } void build(int k,int l,int r){ if(l==r){ mx[k]=1;return ; } int md =(l+r)/2 ; build(k1,l,md);build(k2,md+1,r) ; up(k); } int qq(int k,int l,int r,int x,int y){ if(x<=l && y>=r) return mx[k] ; int md=(l+r)>>1; int t =0 ; if(x<=md) t=max(t,qq(k1,l,md,x,y)); if(y>md) t=max(t,qq(k2,md+1,r,x,y)); return t; } void change(int k,int l,int r,int x,int v){ if(l==r){ mx[k]=v; return ; } int md=(l+r)>>1; if(x<=md ) change(k1,l,md,x,v) ; else change(k2,md+1,r,x,v); up(k) ; } signed main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i],f[i]=1,L=max(L,a[i]); build(1,1,L); for(int i=1;i<=n;i++){ f[i] =max(f[i], qq(1,1,L, a[i],L)+1); change(1,1,L, a[i],f[i]); } int ans= 0; for(int i=1;i<=n;i++) ans=max(ans,f[i]); cout<<ans-1 <<endl; }