先给出例题：P1020 [NOIP1999 普及组] 导弹拦截 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

大佬题解：P1020 [NOIP1999 普及组] 导弹拦截 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)第一个就是

如果是求最长子序列长度，一般可以用dp，时间复杂度O(n^2),使用树状数组优化后，时间复杂度O(nlogn)，在这里就先不讨论了。

在STL里有lower_bound和upper_bound两个函数，都是以二分为原理在有序序列中查找每个数用的。

其中

lower_bound返回的是第一个大于等于x的数的位置，

upper_bound返回的是第一个大于x的数的位置。

本题需要求出最长不上升子序列长度以及最长上升序列长度。

代码：

#include
#include
using namespace std;
const int N = 100000 + 10;
int a[N], s[N], ns[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n = 0, cnt = 1, len = 1;
while (cin >> a[++n])
;
n--;
s[1] = a[1];
ns[1] = a[1];
for (int i = 2; i <= n; ++i) { if (a[i] <= s[cnt]) { s[++cnt] = a[i]; } else { int p = upper_bound(s + 1, s + 1 + cnt, a[i], greater()) - s;
s[p] = a[i];
}
if (a[i] > ns[len])
{
ns[++len] = a[i];
}
else
{
int p = lower_bound(ns + 1, ns + 1 + len, a[i]) - ns;
ns[p] = a[i];
}
}
cout << cnt << " " << len << endl;
return 0;
}