Description：

将 $1$ 到 $N$ 的数字按顺序插入到序列的特定位置中，每次求当前最长上升子序列长度。

$1\leqslant n \leqslant 10^5$

Solution：

最长上升子序列肯定是 $DP$ ，由于插入的顺序是从小到大的，所以插入这个数不会对其他位置的 $DP$ 值产生影响，他插入的位置之前一定都是可以转移到他的，所以在这之前所有数中取个最大值加一就是他的值，于是就是带插入区间最大值，写个 $\text{splay}$ 就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 100010

struct node

{

	int c[2],fa,maxv,val,siz;

	node(){c[0] = c[1] = fa = -1;}

}t[MAXN];

int root = 0;

void maintain(int rt)

{

	t[rt].siz = 1;t[rt].maxv = t[rt].val;

	if(t[rt].c[0] != -1){t[rt].siz += t[t[rt].c[0]].siz;t[rt].maxv = max(t[rt].maxv,t[t[rt].c[0]].maxv);}

	if(t[rt].c[1] != -1){t[rt].siz += t[t[rt].c[1]].siz;t[rt].maxv = max(t[rt].maxv,t[t[rt].c[1]].maxv);}

	return;

}

void connect(int k,int f,int p){t[k].fa = f;t[f].c[p] = k;return;}

int id(int k){return (t[t[k].fa].c[0] == k ? 0 : 1);}

void rotate(int x)

{

	int y = t[x].fa,z = t[y].fa,fx = id(x),fy = id(y);

	connect(t[x].c[fx ^ 1],y,fx);

	connect(y,x,fx ^ 1);connect(x,z,fy);

	maintain(y);maintain(x);

	return;

}

void splay(int x)

{

	while(t[x].fa != -1)

	{

		int y = t[x].fa;

		if(t[y].fa == -1){rotate(x);break;}

		if(id(x) == id(y)){rotate(y);rotate(x);}

		else{rotate(x);rotate(x);}

	}

	root = x;

	return;

}

int find_kth(int k)

{

	int cur = root;

	while(true)

	{

		int ls = 0;

		if(t[cur].c[0] != -1)ls = t[t[cur].c[0]].siz;

		if(k <= ls)cur = t[cur].c[0];

		else if(k > ls + 1){k -= ls + 1;cur = t[cur].c[1];}

		else return cur;

	}

}

void pt(int root)

{

	if(root == -1)return;

	pt(t[root].c[0]);

	cout << t[root].val << " ";

	pt(t[root].c[1]);

	return;

}

int main()

{

	scanf("%d",&n);

	int p;

	t[root].val = 0;t[root].maxv = 0;t[root].siz = 1;

	for(int i = 1;i <= n;++i)

	{

		scanf("%d",&p);

		int pos = find_kth(p + 1);

		splay(pos);

		int f = (t[pos].c[0] != -1 ? t[t[pos].c[0]].maxv : 0);

		t[i].val = f + 1;t[i].maxv = f + 1;t[i].siz = 1;

		if(t[pos].c[0] == -1){t[pos].c[0] = i;t[i].fa = pos;maintain(pos);}

		else

		{

			connect(t[root].c[0],i,0);connect(i,root,0);

			maintain(i);maintain(root);

		}

		printf("%d\n",t[root].maxv);

		pt(root);cout << endl;

	}

	return 0;

}