LIS 问题也就是最长不下降子序列问题，是一个经典的问题。
做法一
我们发现可以动态规划，设 \(f_i\) 表示前 \(i\) 项包含 \(i\) 的 LIS 长度。
有转移方程：
\[f_i=\max_{a_j\leq a_i} f_j +1
\]
可以用 \(O(n^2)\) 的时间复杂度求解
做法二
有一个经典的 \(O(n \log n)\) 求解 LIS 的算法，本质可能类似贪心？
我们设 \(f_i\) 表示长度为 \(i\) 的 LIS 末尾最小为多少。
那么显然，这个 \(f_i\) 具有单调性，可以用二分维护。
具体实现我就不给了，这个不是我们的重点。
做法三
我们都知道经典的 \(O(n \log n)\) 求解 LIS 需要写一个很烦的二分，但是树状数组就不用啦。
观察动态规划转移方程：
\[f_i=\max_{a_j\leq a_i} f_j +1
\]
注意到这就是一个二维偏序问题，所以树状数组轻松解决，对于我这种数据结构爱好者简直是福音。
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL N=1e5+5;
LL n,a[N],t[N],f[N],mx;
LL lowbit(LL x)
{
return x&-x;
}
LL query(LL x)
{
LL ans=0;
while(x)
{
ans=max(ans,t[x]);
x-=lowbit(x);
}
return ans;
}
void update(LL x,LL y)
{
while(x<=n)
{
t[x]=max(t[x],y);
x+=lowbit(x);
}
}
int main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
}
for(int i=1;i<=n;i++)
{
f[i]=query(a[i])+1;
update(a[i],f[i]);
mx=max(f[i],mx);
}
printf("%lld",mx);
}