感觉白学了

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define lowbit(x) x&-x
const int INF = 0x3f3f3f3f3f3f3f3f;
const int N = 1e5 + 10;
const int M = 2e6 + 10;
const int mod = 1e9 + 7;
int n;
int a[N];
int last[N];
int len;
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	last[0]=a[1];
	len=1;
	for(int i=2;i<=n;i++){
		//原来先找到比x大的让后替换它
		//也就是>=x的
		if(a[i]<=last[len-1]){//没有>=的加
			last[len++]=a[i];
			continue;
		}
		int p=upper_bound(last,last+len,a[i],greater<int>())-last;//<的变为>
		last[p]=a[i];
	}
	cout<<len;
	return 0;
}
/*
转化成找到最少有多少个上升子序列
像怎么贪心
对于每个x
要找比x小中最大的
找到了接上去
没有新开一组
新开的时候所有的都>=x
对于每个新开的a[1]a[2]
a[1]>=a[2]为什么
如果a[1]<a[2]a[2]会进入a[1]
a[1]>=a[2]>=a[3]
这就是求最长不上升子序列的长度
贪心就是在数有多长
题目变成最长不上升子序列的长度
讲解最长不上升子序列
首先last降序
我们要让每个last[i]尽可能的大
这样有助于加入新元素
我们在原本降序的last里找到比x大或等于的最小的
x=3
1 2 3 x 4 5
然后修改它
*/