P4309 最长上升子序列

#include<bits/stdc++.h>
using namespace std;
int n,k,l,r,ans;
struct node
{
	int s[2],p,v;//左右儿子,根,当前点
	int MAX,size,flag;//大小&懒标记
	void init(int _v, int _p)
	{
		v=_v;
		p=_p;
		MAX=1;
		size=1;
		return;
	}//初始化
}tr[100005];
int root=1,idx=1;//根，动态空间
void pushup(int x)
{
	tr[x].size=tr[tr[x].s[0]].size+tr[tr[x].s[1]].size+1;
	tr[x].MAX=max(tr[x].v,max(tr[tr[x].s[0]].MAX,tr[tr[x].s[1]].MAX));
	return;
}
void rotate(int x)
{
	int y=tr[x].p,z=tr[y].p;//两个父亲
	int k=tr[y].s[1]==x;//x是y的哪个儿子
	tr[z].s[tr[z].s[1]==y]=x;//Z本来对应y的地方放上x
	tr[x].p=z;//把x的父亲改为z
	tr[y].s[k]=tr[x].s[k^1];
	tr[tr[x].s[k^1]].p=y;//x需要移位的那个儿子的父亲设为y
	tr[x].s[k^1]=y;
	tr[y].p=x;//y的父亲改为x
	pushup(x);
	pushup(y);
	return;
}
void splay(int x,int k)
{
	while(tr[x].p!=k)
	{
		int y=tr[x].p,z=tr[y].p;
		if(z!=k)
		{
			if((x==tr[y].s[0])^(y==tr[z].s[0]))
				rotate(x);//折
			else
				rotate(y);//直
		}
		rotate(x);
	}
	if(!k)
		root=x;
	return;
}
int getpos(int k)
{
	int u=root;
	while(u)
	{
		if(tr[tr[u].s[0]].size>=k)
			u=tr[u].s[0];
		else if(tr[tr[u].s[0]].size+1==k)
			return u;
		else
		{
			k-=tr[tr[u].s[0]].size+1;
			u=tr[u].s[1];
		}
	}
//	return -1;
}
void output(int u)
{
	if(tr[u].s[0])
		output(tr[u].s[0]);//左
	if(tr[u].v>0&&tr[u].v<=n)
		cout<<tr[u].v<<' ';//中
	if(tr[u].s[1])
		output(tr[u].s[1]);//右
	return;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;//>>m;
	tr[idx].size=1;
	tr[++idx].init(0,root);
	tr[root].s[1]=idx;
	for(int i=1;i<=n;i++)
	{
		cin>>k;
		int l=getpos(k+1),r=getpos(k+2);
		splay(l,0);
		splay(r,l);
		tr[r].s[0]=++idx;
		tr[idx].init(i,r);
		splay(getpos(k+2),0);
		ans=max(ans,tr[root].v=max(tr[root].v,tr[tr[root].s[0]].MAX+1));
		cout<<ans<<' ';
	}
	return 0;
}	

本蒟蒻样例没过但求调（