题目
代码（只给出树状数组的）
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n, m;
int a[N], b[N], f[N], tr[N]; //f[i]表示以a[i]为尾的LIS的最大长度
void init()
{
sort(b+1, b+n+1);
m = unique(b+1, b+n+1) - b - 1;
for(int i = 1; i <= n; i++)
a[i] = lower_bound(b+1, b+m+1, a[i]) - b; //离散化，重新按照大小编号为1~m
}
void update(int x, int val)
{
for(; x <= m; x += x & -x)
tr[x] = max(tr[x], val);
}
int query(int x)
{
int retv = 0;
for(; x; x -= x & -x)
retv = max(retv, tr[x]);
return retv;
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i], b[i] = a[i];
init();
int ans = 0;
for(int i = 1; i <= n; i++)
{
f[i] = query(a[i] - 1) + 1; //求以（1~a[i]-1）为尾的LIS的最大长度
ans = max(ans, f[i]);
update(a[i], f[i]);
}
cout << ans;
}
