题目

思路

设f表示以一个位置结尾的最长上升子序列长度。
注意插入的数大小有序，也就是只需要知道每次插入数左边所有位置的f最大值就可以得到它的f。
因为要支持插入操作，用treap/splay维护序列即可

代码

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define N 100007
using namespace std;struct Splay{int val,fa,s[2],size;
}t[N];
struct Node{int num,val;
}a[N];int c[N];
int root,T,n=0,cnt=0,m,num=0,f[N];int max(int x,int y){return x>y? x:y;}
bool Cmp(const Node a,const Node b){return a.val<b.val;}
void update(int p){t[p].size=t[t[p].s[0]].size+t[t[p].s[1]].size+1;}
int wich(int x){return t[t[x].fa].s[0]==x? 0:1;}
void connect(int x,int y,int f){t[x].fa=y;t[y].s[f]=x;}
int lowbit(int x){return x&(-x);}
void add(int x,int val){while(x<=n){c[x]=max(c[x],val);x+=lowbit(x);}}
int query(int x){int ret=0;while(x){ret=max(ret,c[x]);x-=lowbit(x);}return ret;}void rotate(int x){int y=t[x].fa,rt=t[y].fa;int ys=wich(x),rts=wich(y);connect(t[x].s[ys^1],y,ys);connect(y,x,ys^1);connect(x,rt,rts);update(y);update(x);
}void rota(int p){if(wich(p)==wich(t[p].fa)){rotate(t[p].fa);rotate(p);}else{rotate(p);rotate(p);}
}void splay(int p,int to)
{if(!p) return;if(p==to) return;if(to==root) root=p;while(1){if(t[p].fa==to){rotate(p);return;}if(t[t[p].fa].fa==to){rota(p);return;}rota(p);}
}int find(int x)
{int p=root;while(p){if(x<=t[t[p].s[0]].size) p=t[p].s[0];else if(x==t[t[p].s[0]].size+1) return p;else{x-=t[t[p].s[0]].size+1;p=t[p].s[1];}}return 0;
}void insert(int val,int k)
{int l=find(k+1),r=find(k+2);splay(l,root);splay(r,t[root].s[1]);t[++cnt]=(Splay){val,t[root].s[1],{0,0},1};t[t[root].s[1]].s[0]=cnt;update(t[root].s[1]);update(root);splay(cnt,root);
}void dfs(int p)
{if(t[p].s[0]) dfs(t[p].s[0]);if(t[p].val!=INF&&t[p].val!=-INF)a[++num].val=t[p].val;if(t[p].s[1]) dfs(t[p].s[1]);
}int main()
{t[++cnt]=(Splay){-INF,0,{0,2},2};t[++cnt]=(Splay){INF,1,{0,0},1};scanf("%d",&n); int x;root=1;for(int i=1; i<=n; i++)scanf("%d",&x),insert(i,x);dfs(root);for(int i=1; i<=n; i++) a[i].num=i;sort(a+1,a+1+n,Cmp);int ans=0;for(int i=1; i<=n; i++){int maxx=query(a[i].num);add(a[i].num,++maxx);ans=max(ans,maxx);printf("%d\n",ans);}
}