用f[i]表示以i这个值为结尾的最长上升子序列，考虑插入所产生的影响：
1.因为插入顺序从小到大，因此不会改变现有的f值
2.这个点f值就是所有位置在他之前的f取max再+1，而因为序列要支持插入操作，需要使用平衡树来维护
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 100005 4 #define s(p) ch[k][p] 5 int V,n,r,k,s,ans,a[N],ma[N],ra[N],sz[N],ch[N][2]; 6 void New(int k,int x){ 7 a[k]=ma[k]=x; 8 ra[k]=rand(); 9 sz[k]=1; 10 } 11 void up(int k){ 12 sz[k]=sz[s(0)]+sz[s(1)]+1; 13 ma[k]=max(a[k],max(ma[s(0)],ma[s(1)])); 14 } 15 void rotate(int &k,int u,int p){ 16 s(p)=ch[u][p^1]; 17 ch[u][p^1]=k; 18 up(k); 19 up(k=u); 20 } 21 void add(int &k,int x){ 22 if (!k){ 23 New(k=++V,s); 24 return; 25 } 26 bool p=(sz[s(0)]<x); 27 add(s(p),x-p*(sz[s(0)]+1)); 28 up(k); 29 if (ra[s(p)]<ra[k])rotate(k,s(p),p); 30 } 31 int query(int k,int x){ 32 if (!k)return 0; 33 if (x<=sz[s(0)])return query(s(0),x); 34 return max(query(s(1),x-sz[s(0)]-1),max(ma[s(0)],a[k])); 35 } 36 int main(){ 37 srand(time(0)); 38 scanf("%d",&n); 39 for(int i=1;i<=n;i++){ 40 scanf("%d",&k); 41 printf("%d\n",ans=max(ans,s=query(r,k)+1)); 42 add(r,k); 43 } 44 }