一眼切~
重点是按照 $1$~$n$ 的顺序插入每一个数，这样的话就简单了.
#include <cstdio>
#include <algorithm>
#define N 100004
#define lson t[x].ch[0]
#define rson t[x].ch[1]
#define setIO(s) freopen(s".in","r",stdin) , freopen(s".out","w",stdout)
using namespace std;
int cnt,root,n;
struct Node
{
int ch[2],f,maxv,siz,val;
}t[N];
inline void pushup(int x)
{
t[x].siz=t[lson].siz+t[rson].siz+1;
t[x].maxv=max(t[x].val,max(t[lson].maxv,t[rson].maxv));
}
inline int get(int x) { return t[t[x].f].ch[1]==x; }
inline void rotate(int x)
{
int old=t[x].f,fold=t[old].f,which=get(x);
t[old].ch[which]=t[x].ch[which^1],t[t[old].ch[which]].f=old;
t[x].ch[which^1]=old,t[old].f=x,t[x].f=fold;
if(fold) t[fold].ch[t[fold].ch[1]==old]=x;
pushup(old),pushup(x);
}
inline void splay(int x,int &tar)
{
int u=t[tar].f;
for(int fa;(fa=t[x].f)!=u;rotate(x))
if(t[fa].f!=u)
rotate(get(fa)==get(x)?fa:x);
tar=x;
}
void insert(int &x,int ff,int pos,int v)
{
if(!x)
{
x=++cnt,t[x].f=ff,t[x].val=v,pushup(x);
return;
}
int lsize=t[lson].siz;
if(pos<=lsize+1) insert(lson,x,pos,v);
else insert(rson,x,pos-lsize-1,v);
pushup(x);
}
inline int find(int kth)
{
int x=root;
while(1)
{
if(t[lson].siz+1==kth) return x;
if(t[lson].siz>=kth) x=lson;
else kth-=(t[lson].siz+1), x=rson;
}
}
void debug(int x) {
if(lson) debug(lson);
printf("%d ",t[x].val);
if(rson) debug(rson);
}
int main()
{
int i,j,ans=0;
// setIO("input");
scanf("%d",&n);
for(i=1;i<=n;++i)
{
int k,lst;
scanf("%d",&k);
if(k==0) lst=1;
else if(k==i-1) lst=t[root].maxv+1;
else
{
splay(find(k+1),root);
lst=t[t[root].ch[0]].maxv+1;
}
insert(root,0,k+1,lst), splay(cnt,root);
// printf("%d\n",t[root].val);
printf("%d\n",t[root].maxv);
}
return 0;
}