【树状数组维护最值】AcWing 2978. 最长上升子序列

回顾DP方式求解过程：

$p[i]$：原序列

$dp[i]$：以位置 $i$ 为结尾的最长上升子序列；

$dp_i = \max_{j=1}^{i-1}dp_j+1(p_j<p_i)$

也就是说只要知道 $i$ 位置前满足 $a_j<a_i$ 的最大 $dp_j$ 值即可；

权值树状数组维护 $[1,r]$ 的区间最大值，对于 $i$ 位置，在权值树状数组上查询 $[1,a_i-1]$ 的最大值 $t$，这样以 $i$ 为结尾的最长上升子序列的值就是 $t+1$；

#include <bits/stdc++.h>
using namespace std;
	#define LL long long
	#define ls rt<<1
	#define rs rt<<1|1
	#define eps 1e-9
	#define mod 1000000007
	#define MAXN 100005
	#define MS 100005

int n,m;
int a[MS], b[MS], tot;
int p[MS];

int lowbit(int x){
	return x&(-x);
}

void update(int pos,int val){
	for(;pos<=n;pos+=lowbit(pos)) p[pos] = max(p[pos],val);
}

int query(int pos){ // 求 [1,pos] 的最大值 
	int ans = 0;
	for(;pos;pos-=lowbit(pos)) ans = max(ans,p[pos]);
	return ans;
}

void solve(){
	cin >> n;
	for(int i=1;i<=n;i++) cin >> a[i], b[i] = a[i];
	// 离散化 
	sort(b+1,b+n+1);
	tot = 1;
	for(int i=2;i<=n;i++) if(b[i] != b[i-1]) b[++tot] = b[i];
	// 遍历每一个值 
	int ans = 0;
	for(int i=1;i<=n;i++){
		int pos = lower_bound(b+1,b+tot+1,a[i]) - b;
		int cc = query(pos-1)+1;
		ans = max(ans,cc);
		update(pos,cc);
	}
	cout << ans << "\n";
} 

int main() {
	ios::sync_with_stdio(false);
	int ce;
	ce = 1;
//	cin >> ce;
//	scanf("%d",&ce);
	while(ce--){
		solve();
	}



	return 0;
}
/*


*/