题目描述

设有由 $n$ 个 (可能有相同) 的整数组成的数列，记为: {$a_1$、$a_2$、...、$a_n$} 。

例如 {3，18，7，14，10，12，23，41，16，24}。若存在 $i_1 \lt i_2 \lt i_3 \lt \dots \lt i_e$ 且有 $a_{i_1} \lt a_{i_2} \lt ... \lt a_{i_e}$ 则称为长度为 $e$ 的上升子序列。

如上例中 {3，18，23，24} 就是一个长度为 $4$ 的上升序列，同时也是 {3，7，10，12，16，24} 长度为 $6$ 的上升子序列。

程序要求，当原数列给出之后，求出最长的上升子序列的长度。

输入格式

第一行为 $n$，表示 $n$ 个数（$10 \le n \le 100000$）

第二行 $n$ 个整数，数值之间用一个空格分隔（$-10^9 \le a_i \le 10^9$）

输出格式

一个整数，代表最长上升子序列的长度。

数据样例

3
1 2 3

3

7
1 3 7 7 11 8 10

5

题目分析

假设您已经学过了基于动态规划算法求最长上升子序列，在那个算法中，我们用一个 dp[] 数组记录每一个 $_i$ 为序列最后一个数字的情况下的最长上升子序列长度。然后递推 dp[i] 的时候，状态转移方程式：

$dp[i] = max_{j=1}^{j<i}(dp[j]+1)$ ，通过要求每一个 $a_j< a_i$

for(int i=1;i<=n;i++){
	dp[i] = 1;
	for(int j=1; j<i ;j++){
		if(a[j]<a[i])
			dp[i] = max(dp[i], dp[j]+1)
	}
	ans = max(ans, dp[i]);
}

这个算法的时间复杂度为 O($n^2$)，而本题的 $n$ 最大可能到 $10^5$，因此，O($n^2$) 就一定超时了。我们需要找一个更好的算法解决本题。

下面，介绍一个通过树状数组优化最长上升序列的算法，其思想和上述的朴素算法有延续性。

在上面的程序中，我们刷新 dp[i] 的时候，有一个前提条件 if(a[j]<a[i]) ，意思是，只有当 a[i] 是比 a[j] 大的时候，a[i] 才能在 a[j] 为尾项的上升序列基础上延伸。换言之，在 a[i] 前面那些大于等于 a[i] 的 a[j] 都是不会和 a[i] 结合成功的。既然如此，我们就可以按从小到大的顺序把 a[i] 加入到树状数组，加到 a[i] 的时候，比 a[i] 大的那些数还没加入，就不会对结果产生影响；而比 a[i] 小的数，加到了树状数组之后，它们的位置是清晰的（这是树状数组算法的特点），我们很容易遍历这些在前面的 a[j]，找到既在 a[i] 位置的前面，dp[j] 又是最大的，然后算出 dp[i]，然后又把 dp[i] 更新到树状数组，为算后面的 dp[i] 提供数据。

这个算法有几个关键点细节：

1. 如果有几个 a[i] 的值是相等的，那应该先算谁后算谁？因为本题是计算 严格上升序列，序列里面的后项必须大于前项，所以，如果 a[j]==a[i]，a[i] 是不能接在 a[j] 后面的。因此，我们在基于树状数组计算的时候，我们要先计算后面那个。例如 a[7] 和 a[11] 均为 107，我们先算 a[11]，在这个时候 a[7] 并没有加入树状数组，因此就最大值就不可能出在 7 的位置，dp[11] 肯定不会基于 dp[7] 的基础上延伸出来。而算完 a[11] 之后，我们接着算 a[7]，虽然 a[11] 已经在树状数组中反映出来，但是 11 在 7 的后方，前方的数肯定不能在后方的某个数字之后延续，所以 dp[7] 也和 dp[11] 无关。

2. 我们在学树状数组的模板题的时候，树状数组 c[] 里存的是区间和，c[i] 管理着若干个 a[]，c[i] 存的就是这些被管理单元的和。而在这题，同样是树状数组管理 a[] 元素的思想，但是存的就不是 a[] 的区间和了，存的是区间最大值。我们算 dp[i] 的时候，是要算 i 前面的 dp[] 最大值，也就是 用 [1,i-1] 的 dp 最大值加 1 得到 dp[i]，通过树状数组的算法，区间 [1,i-1] 会被切割成若干个子区间。

3. 利用公式 $dp[i] = (\max_{j=1}^{j<i} dp[j]) + 1$算出 dp[i] 之后 ,我们需要把 dp[i] 更新到树状数组。dp[i] 位置的树状数组单元被更新了，它的上级（后继单元）也要更新，因为后继单元是管着自己的，自己变大了，管理单元的最大值可能也会变大。但是，一旦自己的更新之后还是没有管理单元大，那就不需要在刷新下去了，因为管理着的上级是比管理着大的，后继越来越大，既然没有当前这个管理单元大，自然也不会比后面的后继单元大了，刷新可以终止。

完善程序

#include<bits/stdc++.h>
using namespace std;
#define lowbit(i) ((-i)&i)
int n,c[100001],ans,dp[100001];

struct Num{
	int num,pos;
	bool operator < (const Num &other ) const {
		return this->num<other.num ||(this->num==other.num && this->pos __填空(1)__ other.pos);
	}
}a[100001];

int query(int x){ // 查询 c[1] 到 c[x] 的最大值
	int ret = 0;
	for(int i=x;i>0;i-=lowbit(i))
		if(ret < c[i]) __填空(2)__;
	return ret;
}

void update(int x,int k){ // 从 x 未知开始，刷新所有管理单元的信息（树状数组单元里存的是最大值）
	for(int i=x;i<=n;i+=lowbit(i)){
		if(c[i]<k) __填空(3)__;
		else __填空(4)__;
	}
}

int main()
{
	scanf("%d",&n);

	for(int i=1;i<=n;i++){
		scanf("%d",&a[i].num);
		a[i].pos = i;
	}
	sort(a+1,a+1+n);

	for(int i=1;i<=n;i++){
		dp[i] = __填空(5)__;
		ans = max(ans,dp[i]);
		update(__填空(6)__);
	}

	cout<<ans;

	return 0;
}

填空(1):{{ input(1) }}

填空(2):{{ input(2) }}

填空(3):{{ input(3) }}

填空(4):{{ input(4) }}

填空(5):{{ input(5) }}

填空(6):{{ input(6) }}