最长上升子序列

 最长上升子序列$(LongestIncreasingSubsequence)$，简称$LIS$，也有些情况求的是最长非降序子序列，二者区别就是序列中是否可以有相等的数。

$O(n^2)$的做法——暴力枚举

 我们知道，对于最长上升子序列，假设我们用$f_i$表示出当前位置为$i$的最长上升子序列的长度，可以写出一个$DP$方程
$$f_i=\underset{j<i}{\max }(f_j)+1(a_j<a_i)$$
 因此，对于每一个$i$，我们只需要枚举$i$之前的$j$的，依次转移比大小即可。复杂度显然是$O(n^2)$的。

$O(n\log n)$的做法——树状数组优化

 其实$LIS$是一个典型的二维偏序问题，二维偏序的核心思路就是通过树状数组进行优化。
 我们再来回顾$O(n^2)DP$的状态转移方程：
$$f[i]=\max (f[j])+1(1\le j<i，A[j]\le A[i])$$
 我们在递推$f$数组的时候，每次都要把$f$数组扫一遍求$f[j]$的最大值，时间开销比较大。我们可以借助数据结构来优化这个过程。用树状数组来维护$f$数组（据说分块也是可以的，但是分块是$O(n\sqrt{n})$的时间复杂度，不如树状数组跑得快），首先把$A$数组从小到大排序，同时把$A[i]$在排序之前的序号记录下来。然后从小到大枚举$A[i]$，每次用编号小于等于$A[i]$编号的元素的$LIS$长度$+1$来更新答案，同时把编号大于等于$A[i]$编号元素的$LIS$长度$+1$。因为$A$数组已经是有序的，所以可以直接更新。有点绕，具体看代码。

#include
#define in read()
#define MAXN 100050
#define re register
#define INF (1<<30)
#define lb(x) x&(-x)
using namespace std;

struct node{
	int id,val;
	bool operator < (const node &rhs)const{
		return val==rhs.val?id<rhs.id:val<rhs.val;
	}
}a[MAXN];
int n,t[MAXN],ans=0;

inline int read(){
	int x=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
	return x*f;
}

inline void update(int x,int v){
	for(;x<=n;x+=lb(x)){t[x]=max(t[x],v);}
}

inline int query(int x){
	int res=-INF;
	for(;x;x-=lb(x)){res=max(res,t[x]);}
	return res;
}

int main(){
	n=in;
	for(re int i=1;i<=n;i++)a[i].val=in,a[i].id=i;
	sort(a+1,a+n+1);
	for(re int i=1;i<=n;i++){
		int maxx=query(a[i].id);
		update(a[i].id,++maxx);
		ans=max(ans,maxx);
	}
	cout<<ans<<'\n';
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

 让我们理性思考一下这个算法的正确性，因为我们按照数的大小进行的排序，那么后被扫描到的数就一定比先扫描到的数更大，满足了一个条件。此时我们只需要再满足大的数的下标比小的数的下标大即可，而树状数组巧妙解决了这个问题。