题目：codevs 1576 最长严格上升子序列
链接：http://codevs.cn/problem/1576/
优化的地方是 1到i-1 中最大的 f[j]值，并且A[j]<A[i] 。根据数星星的经验，一个点一个点更新可以解决1到i-1的问题，然后线段树是维护最大值，那么A[j]<A[i]的条件就用查询区间保证，即查询：1到A[i]的f[i]最大值。为了不溢出，因此需要离散化。
附代码：
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn=; int f[maxn],n,maxv[maxn*]; struct u
{
int v,r;
bool operator <(const u &rhs) const
{
return v<rhs.v;
}
}A[maxn]; bool cmp(u a,u b)
{
return a.r<b.r;
} int p,v;
void update(int o,int L,int R)
{
if(L==R) maxv[o]=v;
else
{
int M=(L+R)/;
if(p<=M) update(o*,L,M); else update(o*+,M+,R);
maxv[o]=max(maxv[o*],maxv[o*+]);
}
} int y1,y2,ans;
void query(int o,int L,int R)
{
if(y1<=L && R<=y2) ans=max(ans,maxv[o]);
else
{
int M=(L+R)/;
if(y1<=M) query(o*,L,M);
if(y2>M) query(o*+,M+,R);
}
} int main()
{
cin>>n;
for(int i=;i<=n;i++)
{
cin>>A[i].v;
f[i]=;
A[i].r=i;
} sort(A+,A+n+);
for(int i=;i<=n;i++) A[i].v=i;
sort(A+,A+n+,cmp); p=A[].v,v=;
update(,,n);
for(int i=;i<=n;i++)
{
y1=,y2=A[i].v,ans=;
query(,,n);
f[i]=ans+;
p=A[i].v,v=f[i];
update(,,n);
}
cout<<f[n];
return ;
}