$f[i]=max(f[j]+1,f[i])(i<=j)$
把整个过程在平衡树上实现,因为加入的数字单调递增,所以f[N]始终不为0
fhq取得max的过程是要和本位比较的,因为v递增,所以dp[v]只会一次修改,可以作为本位数值在max时发挥作用
#include<bits/stdc++.h>
#define ls(x) tr[x].l
#define rs(x) tr[x].r
#define t(x) tr[x]
#define tls(x) t(ls(x))
#define trs(x) t(rs(x))
using namespace std;
const int N= 1e5+9;
typedef long long ll;
int x,y,z;
int cnt,tot;
int ans,n;
int root,p;
int dp[N];
struct node
{
int l,r,key;
int v,siz ;
int len;
void init(int l,int val)
{
key= rand();
v=val;
len =l;
siz = 1;
l=r=0;
}
}tr[N];
int new_node(int len,int val)
{
t(++tot).init(len,val);
dp[val]=len;
return tot;
}
void up(int x)
{
t(x).siz = tls(x).siz +trs(x).siz+1;
t(x).len=max({dp[t(x).v],tls(x).len,trs(x).len});
}
void split(int p,int k,int &x,int &y)
{
if(p==0){x=y=0;return;}
if(tls(p).siz<k)
{
x=p;
split(rs(x),k-1-tls(p).siz,rs(x),y);
up(x);
}
else
{
y=p;
split(ls(y),k,x,ls(y));
up(y);
}
}
int merge(int x,int y)
{
if(x==0||y==0)return x+y;
if(t(x).key<t(y).key)
{
rs(x)=merge(rs(x),y);
up(x);
return x;
}
else
{
ls(y)=merge(x,ls(y));
up(y);
return y;
}
}
void add(int &root,int pos,int num)
{
split(root,pos,x,z);
int p= new_node(t(x).len+1,num);
root=merge(merge(x,p),z);
}
signed main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int p;
scanf("%d",&p);
add(root,p,i);
printf("%d\n",t(root).len);
}
return 0;
}