杨氏图表，维护若干个单调不下降队列。
每次新加入一个数时，先考虑第一个队列：
如果可以放在最后，则放在最后。
否则找到最小的可以替换的替换掉，再将替换的数放入第二个队列，以此类推。
最后$ans_i=\sum_{j=1}^i t_j$。
时间复杂度$O(n^2\log n)$。
#include<cstdio>
#define N 5005
int n,i,x,t[N];unsigned char q[N][N];
void up(int p,int x){
if(x>=q[p][t[p]]){q[p][++t[p]]=x;return;}
int l=1,r=t[p],mid,u;
while(l<=r)if(q[p][mid=(l+r)>>1]>x)r=(u=mid)-1;else l=mid+1;
up(p+1,q[p][u]),q[p][u]=x;
}
int main(){
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&x),up(1,x);
for(i=1;;i++){
printf("%d\n",t[i]+=t[i-1]);
if(t[i]==n)return 0;
}
}
BZOJ1175 : [Balkan2007]The stairways of Saharna
原文：http://www.cnblogs.com/clrs97/p/5143821.html