BZOJ_3173_[Tjoi2013]最长上升子序列_splay

Description

给定一个序列，初始为空。现在我们将1到N的数字插入到序列中，每次将一个数字插入到一个特定的位置。每插入一个数字，我们都想知道此时最长上升子序列长度是多少？

Input

第一行一个整数N，表示我们要将1到N插入序列中，接下是N个数字，第k个数字Xk，表示我们将k插入到位置Xk（0<=Xk<=k-1,1<=k<=N）

Output

N行，第i行表示i插入Xi位置后序列的最长上升子序列的长度是多少。

Sample Input

3
0 0 2

Sample Output

1
1
2

HINT

100%的数据 n<=100000

分析：由于数字是升序插入的，因此每次操作只会对它一个数产生影响。

问题转化为：插入一个数，查询某个位置前面的最大值。

直接用平衡树维护即可。

代码：

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <math.h>

using namespace std;

#define N 100050

#define ls ch[p][0]

#define rs ch[p][1]

#define get(x) (ch[f[x]][1]==x)

int f[N],rt,ch[N][2],siz[N],cnt,val[N],mx[N],n,ans;

void pushup(int p) {

	if(p) {

		siz[p]=siz[ls]+siz[rs]+1;

		mx[p]=max(max(mx[ls],mx[rs]),val[p]);

	}

}

void rotate(int x) {

	int y=f[x],z=f[y],k=get(x);

	ch[y][k]=ch[x][!k]; f[ch[y][k]]=y;

	ch[x][!k]=y; f[y]=x; f[x]=z;

	if(z) ch[z][ch[z][1]==y]=x;

	pushup(y); pushup(x);

	if(rt==y) rt=x;

}

void splay(int x,int y) {

	for(int fa;(fa=f[x])!=y;rotate(x))

		if(f[fa]!=y)

			rotate(get(fa)==get(x)?fa:x);

}

int find(int x) {

	int p=rt;

	while(1) {

		if(x<=siz[ls]) p=ls;

		else {

			x-=siz[ls]+1;

			if(!x) return p;

			p=rs;

		}

	}

}

int main() {

	scanf("%d",&n);

	int i,x,y,p;

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

		scanf("%d",&x);

		if(x==0) {

			if(!rt) {

				rt=i; val[i]=1; siz[i]=1; pushup(i);

			}

			else {

				p=find(1);

				splay(p,0);

				val[i]=1; siz[i]=1; f[i]=p; ls=i;

				pushup(i); pushup(p);

			}

		}else if(x==i-1) {

			p=find(i-1);

			splay(p,0);

			val[i]=mx[p]+1; siz[i]=1; f[i]=p; rs=i;

			pushup(i); pushup(p);

		}else {

			int tmp=x;

			x=find(x); p=find(tmp+1);

			splay(x,0); splay(p,x);

			val[i]=max(mx[ch[x][0]],val[x])+1; siz[i]=1; f[i]=p; ls=i;

			pushup(i); pushup(p); pushup(x);

		}

		ans=max(ans,val[i]);

		printf("%d\n",ans);

	}

}

秒客网