luogu P1020 导弹拦截

题目链接：luogu P1020 导弹拦截

题目大意：

题解：
寻找一个最长上升序列和一个最长不上升序列，通过二分的方法寻找替换的位置。

#include <algorithm>
#include <iostream>
using namespace std;
#define N 100010

int a[N], f1[N], f2[N], n;

int main() {
    while (cin >> a[++n]);
    n--;
    int len1 = 1, len2 = 1;
    f1[1] = a[1];
    f2[1] = a[1];
    for (int i = 2; i <= n; ++i) {
        if (f1[len1] >= a[i]) {
            f1[++len1] = a[i];
        } else {
            int p1 = upper_bound(f1 + 1, f1 + 1 + len1, a[i], greater<int>()) - f1;
            f1[p1] = a[i];
        }
        if (f2[len2] < a[i]) {
            f2[++len2] = a[i];
        } else {
            int p2 = lower_bound(f2 + 1, f2 + 1 + len2, a[i]) - f2;
            f2[p2] = a[i];
        }
    }
    cout << len1 << endl << len2;
    return 0;
}