nlogn版最长递增子序列。线段树。（其实常数蛮大的。。。。）
#include<iostream>
#include<cstring>
#include<algorithm>
#define maxn 50050
using namespace std;
int n,ls[maxn<<],rs[maxn<<],val[maxn<<],root,tot=;
struct pnt
{
int id,val;
}p[maxn];
bool cmp(pnt x,pnt y)
{
if (x.val!=y.val) return x.val<y.val;
return x.id>y.id;
}
void addpnt(int id,int val)
{
p[id].id=id;
p[id].val=val;
}
void build(int &now,int left,int right)
{
now=++tot;val[now]=;
if (left==right) return;
int mid=(left+right)>>;
build(ls[now],left,mid);
build(rs[now],mid+,right);
}
void pushup(int now)
{
val[now]=max(val[ls[now]],val[rs[now]]);
}
int ask(int now,int left,int right,int l,int r)
{
if ((left==l) && (right==r))
return val[now];
int mid=(left+right)>>;
if (r<=mid) return ask(ls[now],left,mid,l,r);
else if (l>=mid+) return ask(rs[now],mid+,right,l,r);
else return max(ask(ls[now],left,mid,l,mid),ask(rs[now],mid+,right,mid+,r));
}
void modify(int now,int left,int right,int pos,int x)
{
if ((left==right) && (left==pos))
{
val[now]=x;
return;
}
int mid=(left+right)>>;
if (pos<=mid) modify(ls[now],left,mid,pos,x);
else modify(rs[now],mid+,right,pos,x);
pushup(now);
}
int main()
{
scanf("%d",&n);
build(root,,n);
for (int i=;i<=n;i++)
{
int x;
scanf("%d",&x);
addpnt(i,x);
}
sort(p+,p+n+,cmp);
for (int i=;i<=n;i++)
{
int regis;
if (p[i].id==) regis=;
else regis=ask(root,,n,,p[i].id-);
modify(root,,n,p[i].id,regis+);
}
printf("%d\n",val[]);
return ;
}