经典的 LIS 问题不再赘述，利用 DP 的思想可以做到 \(O(n^2)\)，利用单调队列优化可以做到 \(O(n\log n)\)，然而单调队列的做法对于我等蒟蒻来说还是有点复杂的，因此这里介绍一种更初等的，更直接的，更好写的基于 BIT 的做法。

跳出 DP 的框架，我们定义 \(p[x]\) 为以 \(x\) 结尾的 LIS 的长度，我们从左到右地扫，同时更新 \(p[x]\) 的值，最后 \(p\) 当中的最大值即为所求的答案。

假设我们扫到数 \(x\)，很明显它可以接在任何最后一个数小于 \(x\) 的上升子序列的后面，因此我们做如下的更新： \[ p[x] = \max \begin{cases} p[x] \\ \max_{1 \le i < x} \{p[i]\} + 1 \end{cases} \] 我们看到，更新操作需要查询前缀最大值，又因为我们发现 \(p[x]\) 的更新一定是单调不降的，因此得以使用 BIT 维护（以上条件任意一个不满足都只能使用线段树了），思路较单调队列的直接，之于 \(x\) 范围的问题，离散化一下即可，时间复杂度自然也是 \(O(n \log n)\)，代码如下：

#include <cstdio>
#include <algorithm> 

using namespace std;
#define max(a, b) ((a) > (b) ? (a) : (b))
const int N = 10010;
int n, ans, tot, a[N], d[N], bit[N];

inline int query(int x) {
    int ret = 0;
    for (; x; x -= x & -x) ret = max(ret, bit[x]);
    return ret;
}

inline void update(int x, int d) {
    for (; x <= tot; x += x & -x) bit[x] = max(bit[x], d);
}

int main() {
    scanf("%d", &n); ans = 0;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    copy(a + 1, a + 1 + n, d + 1);
    sort(d + 1, d + 1 + n);
    tot = unique(d + 1, d + 1 + n) - d - 1;
    for (int i = 1; i <= n; i++) {
        int x = lower_bound(d + 1, d + 1 + tot, a[i]) - d;
        update(x, query(x - 1) + 1);
    }
    printf("%d\n", query(tot));
    return 0;
}