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