容易发现如果求出最后的序列，只要算一下LIS就好了。序列用平衡树随便搞一下，这里种一棵splay。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } #define N 100010 int n,tree[N],cnt=0; struct data { int x,f; bool operator <(const data&a) const { return x<a.x; } }a[N]; namespace Splay { struct data{int fa,ch[2],s;}tree[N]; int root=0; int whichson(int k){return tree[tree[k].fa].ch[1]==k;} void up(int k){tree[k].s=tree[tree[k].ch[0]].s+tree[tree[k].ch[1]].s+1;} void move(int k) { int fa=tree[k].fa,gf=tree[fa].fa,p=whichson(k); if (fa) tree[gf].ch[whichson(fa)]=k;tree[k].fa=gf; tree[fa].ch[p]=tree[k].ch[!p],tree[tree[k].ch[!p]].fa=fa; tree[k].ch[!p]=fa,tree[fa].fa=k; up(fa),up(k); } void splay(int k) { while (tree[k].fa) { int fa=tree[k].fa; if (tree[fa].fa) if (whichson(fa)^whichson(k)) move(k); else move(fa); move(k); } root=k; } void ins(int &k,int s,int x,int from) { if (!k) {k=x,tree[k].s=1,tree[k].fa=from;return;} if (tree[tree[k].ch[0]].s>=s) ins(tree[k].ch[0],s,x,k); else ins(tree[k].ch[1],s-tree[tree[k].ch[0]].s-1,x,k); } void dfs(int k) { if (tree[k].ch[0]) dfs(tree[k].ch[0]); a[++cnt].x=k; if (tree[k].ch[1]) dfs(tree[k].ch[1]); } } int query(int k){int s=0;while (k) s=max(s,tree[k]),k-=k&-k;return s;} void ins(int k,int x){while (k<=n) tree[k]=max(tree[k],x),k+=k&-k;} int main() { #ifndef ONLINE_JUDGE freopen("bzoj3173.in","r",stdin); freopen("bzoj3173.out","w",stdout); const char LL[]="%I64d "; #else const char LL[]="%lld "; #endif n=read(); for (int i=1;i<=n;i++) { int x=read(); Splay::ins(Splay::root,x,i,0);Splay::splay(i); } Splay::dfs(Splay::root); for (int i=1;i<=n;i++) a[i].f=query(a[i].x)+1,ins(a[i].x,a[i].f); sort(a+1,a+n+1); for (int i=1;i<=n;i++) a[i].f=max(a[i].f,a[i-1].f),printf("%d ",a[i].f); return 0; }