不知道为什么,这个题,竟然没有人用树状数组优化。
我们发现$n\leq 10^6$,我们按照第一个的$O(n^2)$做法自然会$T$到上天,那么我们就可以考虑优化,既然我们的状态转移是$$f_{i} = max(f_{j} +1 , f_i) | j < i$$
然后我们就发现$f_i$是一个一维的,那么我们就必然无法再在这个状态上进行优化,那么我们就考虑优化状态转移,同样的,我们显然可以发现$O(N \times log N)$是可过的,那么我们考虑树状数组优化,进行查询。自然此题也可以用线段树进行优化,查询的复杂度也是$O(logN)$的,显然都是可以掉这道题的。
首先我们显然是不需要知道么每一个点权值,我们只关心它们的大小关系,那么我们可以离散化一下。
$Code$:
/*
by : Zmonarch
知识点 ; 最长上升子序列
做法: 树状数组优化
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define int long long
#define lowbit(x) x&(-x)
using namespace std ;
const int kmaxn = 1e6 + 10 ;
inline int read()
{
int x = 0 , f = 1 ; char ch = getchar() ;
while(!isdigit(ch)) { if(ch == '-') f = - 1 ; ch = getchar() ; }
while( isdigit(ch)) { x = x * 10 + ch - '0' ; ch = getchar() ; }
return x * f ;
}
int n , a[kmaxn] , f[kmaxn] ;
int v[kmaxn] ;
void update(int x , int val)
{
for(int i = x ; i <= n ; i += lowbit(i))
{
f[i] = max(f[i] , val) ;
}
}
int query(int x )
{
int ans = 0 ;
for(int i = x ; i ; i -= lowbit(i))
{
ans = max(ans , f[i]) ;
}
return ans ;
}
signed main()
{
n = read() ;
int ans = 0 ;
for(int i = 1 ; i <= n ; i++) a[i] = read() , v[i] = a[i] ;
sort(v + 1 , v + n + 1 ) ;
int len = (v + 1 , v + n + 1 ) - v ;
for(int i = 1 ; i <= n ; i++)
{
int p = lower_bound(v , v + len , a[i]) - v + 1 ;
ans = max(ans , query(p - 1) + 1) ;
update(p , query(p - 1) + 1 ) ;
}
printf("%lld\n" , ans) ;
return 0 ;
}