LIS

LIS ⁡ \operatorname{LIS} LIS

题目链接： AtCoder Chokudai SpeedRun 001 H ⁡ \operatorname{AtCoder\ Chokudai\ SpeedRun\ 001\ H} AtCoder Chokudai SpeedRun 001 H / luogu AT2827 ⁡ \operatorname{luogu\ AT2827} luogu AT2827

题目大意

来自洛谷：

样例输入1

5
3 1 5 4 2

样例输出1

2

样例输入2

6
1 2 3 4 5 6

样例输出2

6

样例输入3

7
7 6 5 4 3 2 1

样例输出3

1

样例输入4

20
19 11 10 7 8 9 17 18 20 4 3 15 16 1 5 14 6 2 13 12

样例输出4

6

数据范围

1 ≤ N ≤ 100 , 000 1\leq N\leq 100,000 1≤N≤100,000

思路

就是一道普通的 LIS 。

就按 nlogn 的算法来做即可。

洛谷交不了，可以在 AtCoder 上面交。

点我查看 LIS 模板题的题解！

代码

#include<cstdio>
#include<iostream>

using namespace std;

int n, a[100001], shang[100001], lef, righ, shang_num;

int main() {
	shang[0] = -2147483647;
	
	scanf("%d", &n); 
	
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		if (a[i] > shang[shang_num]) {
			shang_num++;
			shang[shang_num] = a[i];
		}
		else {
			lef = 0, righ = shang_num;
			while (lef < righ) {
				int mid = (lef + righ) >> 1;
				if (shang[mid] >= a[i]) righ = mid;
					else lef = mid + 1;
			}
			shang[lef] = min(shang[lef], a[i]);
		}
	}
	
	printf("%d", shang_num);
	
	return 0;
}