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
0 0 2
Sample Output
1
1
2
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);
}
}