导弹拦截和二维偏序
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
input: 389 207 155 300 299 170 158 65 output : 6 2
导弹之间形成了一个二维偏序关系，两个维度分别为发射时间先后和高度 (time, height)
分别以其为横轴和纵轴可以画出下图：
▲
│
│ │
│ ▼ 399 │
│ ▼ 300 │
│ ▼ 299 │
│ ▼ 207 │
│ ▼ 170 │
│ ▼ 158 │
│ ▼ 155 │
│ ───────────────────────────────────────────┼────
│ │ ▼ 65
└───────────────────────────────────────────────────────────────►
可以看出假如不保留足够的信息，无法区分 65 这个导弹的上家是拦截 155 还是 158 更好，因而这里不能考虑贪心
朴素 dp
迭代到 65 时，不会考虑此前高度小于 65 的导弹，也不会考虑在 65 之后才要拦截的导弹，因而只需要考察上方图中 65 左上侧的导弹
于是有一个很简单的 dp 思路：以 dp1[i] 表示拦截第 i 个导弹的最长序列长度，则
树状数组
可以看到，如果能够考虑从 158 这个导弹接龙，则一定不用考虑从 170 这个导弹接龙，因为 170 在 158 的左上侧
这说明有重复信息可以利用，有优化空间
重新审查迭代过程，发现可以通过维护一个区间的值来利用这个信息：
当 155 高度的导弹迭代完成时，以其结尾的导弹序列长度为 dp2[155]，则此后高度在 [1, 155] 之间的导弹，起码能成为长度 dp2[155] + 1 的导弹序列结尾
因此，通过维护 [1, height[i]] 的区间最大值，可以立刻得到新导弹能接上的最长序列
可以通过树状数组来维护这样的区间值
单调性
可以看出，上方树状数组的做法中，若以 max[i] 表示 [1, i] 的区间最大值，则其是一个单调不增序列，这是由它的定义决定的
其实这里已经没有什么优化空间了，因为维护这样的区间最值，基本上也就是树状数组这个数据结构的最大能力了
其他题解不用树状数组的，基本上都是利用了这个单调性：
回过头来看上面的二维偏序图，不能仅仅维护图中的凸包络面：
▲
│ ▼
│ ▼
│ ▼ ▼ x
│ ▼ ▼ ▼ ▼ x
│ ▼
│ ▼
│ ▼ y
│ ▼ ▼ ▼ x4
│ ▼
│ ▼
│ x3
│ x2
│ x1
│ A
──┴─────────────────────────────────────────────────────────►
图中迭代到 A 时，不能仅考察标为 x 的所有点，尽管其余所有点都包络在这些点的左上侧。（反例是接下来来了一个高度在 [x4, y] 之间的点）
实际上，所有在 “最右侧” 的点，都应该维护，唯一能保证可以丢弃的只有高度相同的点：
▲
│ x
│ x
│ ▼ ▼ x
│ ▼ ▼ ▼ ▼ x
│ x
│ x
│ ▼ x
│ ▼ ▼ ▼ x4
│ x
│ x
│ x3
│ x2
│ x1
│ A
──┴─────────────────────────────────────────────────────────►
（所有标为
x的点，接下来都有可能用到）
与此同时，这些点当中也有点可以不必维护：比如 x1, x2, x3 的最长导弹拦截序列都是 2，假如
A同时小于这三者，则这三者对于A来说是等价的- 但如果
A小于x3却大于x2，则只需要考虑x3，而不必考虑x1, x2
因此，x3 是一定要保留的，而 x1, x2 却是可有可无的，综上，在这条包络线当中，对于最长序列长度相等的点，只需维护其中高度最高的点
或者，由于题目没有要求输出具体点，因而只需要维护最高高度，而不必关注具体是哪个点
于是仅仅需要维护 dp3[i] 表示长为 i 的拦截序列的尾部最大高度。这已经是需要维护的最少的信息
可以看出这个信息与上方树状数组中单调性等价：其实质是维护区间最大值的端点
同样可以看出，随着迭代过程，对于任意长度 i，dp3[i] 是只增不减的，这对应了上方树状数组的区间端点只增不减
第二问
据说有 Dilworth 定理，其在此题中的体现是：
将一个序列剖成若干个单调不升子序列的最小个数等于该序列最长上升子序列的个数
我这里是直接贪心
代码（树状数组）
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
const int MAX_VALUE = 5e4 + 50;
template <std::size_t N> struct BIT {
int c[N] = {0};
static inline int lowbit(const int x) { return x & -x; }
/// update value in [1, i] with n
void update(int n, int i) {
while (i > 0 && c[i] < n) {
c[i] = n;
i -= lowbit(i);
}
}
int get(int i) {
int ans = 0;
while (i <= N) {
ans = std::max(ans, c[i]);
i += lowbit(i);
}
return ans;
}
};
int main() {
int n = 0;
int a[(int)1e5 + 50];
while (std::cin >> a[n++]) {
};
n -= 1;
if (n == 0) {
std::cout << "0\n0" << std::endl;
return 0;
}
auto bit = BIT<MAX_VALUE>{};
for (int i = 0; i < n; i++) {
bit.update(bit.get(a[i]) + 1, a[i]);
}
auto v2 = std::vector<int>{a[0]};
for (int i = 1; i < n; i++) {
auto tmp = std::lower_bound(v2.begin(), v2.end(), a[i]);
if (tmp == v2.end()) {
v2.push_back(a[i]);
} else {
*tmp = a[i];
}
}
std::cout << bit.get(1) << std::endl << v2.size();
return 0;
}