根據題意很容易得到最原始的做法：

#include<iostream> #include<cstdio> #include<cstring> #include<vector> using namespace std; const int N=100005; int n,m,f[N]; int main(){scanf("%d",&n);int x;for(int i=1;i<=n;i++){scanf("%d",&x);for(int j=i-1;j>=x+1;j--)f[j+1]=f[j];int maxn=0;for(int j=0;j<=x;j++)maxn=max(maxn,f[j]);f[x+1]=maxn+1;maxn=0;for(int j=0;j<=i;j++)maxn=max(maxn,f[j]);printf("%d\n",maxn);}return 0; }

接著，用splay，fhq_treap…這些數據結構實現在 f[ ] 數組中插入一個數、求區間最大值的操作就可以了

#include<iostream> #include<cstdio> #include<cstring> using namespace std; #define Key_value ch[ch[root][1]][0] const int N=100005*2; const int inf=0x3f3f3f3f; int fa[N],ch[N][2],key[N],sz[N],maxn[N]; int root,tot1; int s[N],tot2; int n; void NewNode(int &x,int pre,int k){if(tot2) x=s[tot2--];else x=++tot1;ch[x][0]=ch[x][1]=0;fa[x]=pre;sz[x]=1;key[x]=maxn[x]=k; } void push_up(int x){sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;maxn[x]=key[x];if(ch[x][0]) maxn[x]=max(maxn[x],maxn[ch[x][0]]);if(ch[x][1]) maxn[x]=max(maxn[x],maxn[ch[x][1]]); } void rotate(int x,int d){int y=fa[x];ch[y][!d]=ch[x][d];fa[ch[x][d]]=y;if(fa[y]) ch[fa[y]][ch[fa[y]][1]==y]=x;fa[x]=fa[y];ch[x][d]=y;fa[y]=x;push_up(y); } void splay(int x,int goal){while(fa[x]!=goal){if(fa[fa[x]]==goal)rotate(x,ch[fa[x]][0]==x);else{int y=fa[x];int d=(ch[fa[y]][0]==y);if(ch[y][d]==x){rotate(x,!d);rotate(x,d);}else{rotate(y,d);rotate(x,d);}}}push_up(x);if(goal==0) root=x; } int get_kth(int x,int k){int t=sz[ch[x][0]]+1;if(t==k) return x;if(t>k) return get_kth(ch[x][0],k);else get_kth(ch[x][1],k-t); } void update_insert(int x,int p){splay(get_kth(root,x+1),0);splay(get_kth(root,x+2),root);NewNode(Key_value,ch[root][1],p);push_up(ch[root][1]);push_up(root); } int query_maxn(int l,int r){splay(get_kth(root,l),0);splay(get_kth(root,r+2),root);return maxn[Key_value]; } int main(){NewNode(root,0,inf);NewNode(ch[root][1],root,inf);NewNode(Key_value,ch[root][1],0);scanf("%d",&n);int x,p;for(int i=1;i<=n;i++){scanf("%d",&x);x++;p=query_maxn(1,x)+1;update_insert(x,p);printf("%d\n",query_maxn(1,i+1));}return 0; }

(加1減1什么的真的快把我調瘋了)

總結

以上是生活随笔為你收集整理的[BZOJ 3173] [TJOI 2013] 最长上升子序列(splay)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。