题目大意：完成一颗splay树。
思路：模板题，学着还是很有意思的。
学习splay树：蒟蒻yyb
该题模板：汪立超
#include<bits/stdc++.h> #define CLR(a,b) memset(a,b,sizeof(a)) using namespace std; typedef long long ll; int root,N=0,n,p,q; int fa[100001],c[100001][2],size[100001],sp[100001]; void rot(int x) { int y=fa[x],k=(c[y][0]==x); size[y]=size[c[y][k]]+size[c[x][k]]+1; size[x]=size[c[x][!k]]+size[y]+1; c[y][!k]=c[x][k]; fa[c[y][!k]]=y; fa[x]=fa[y]; if(fa[y])c[fa[y]][c[fa[y]][1]==y]=x; c[x][k]=y; fa[y]=x; } void rots(int x,int g) {//splay for(int y=fa[x]; y!=g; rot(x),y=fa[x]) if(fa[y]!=g) rot((x==c[y][0])==(y==c[fa[y]][0])?y:x); if(g==0) root=x; } void insert(int x) {//插入 int y=root; while(c[y][x>sp[y]]) y=c[y][x>sp[y]]; sp[++N]=x; c[N][0]=c[N][1]=0; fa[N]=y; if(y)c[y][x>sp[y]]=N; rots(N,0); } void del(int x) {//删除 int y=root; while(sp[y]!=x) y=c[y][x>sp[y]]; rots(y,0); y=c[root][1]; bool b; if(!y) b=1,y=c[root][0]; else b=0; while(c[y][b]) y=c[y][b]; rots(y,root); c[y][b]=c[root][b]; fa[c[root][b]]=y; fa[y]=0; root=y; size[y]=size[c[y][!b]]+size[c[y][b]]; } int rank(int x) {//输出x的rank int y=root,ans=0; if(x==918145) { printf(""); } while(y) if(x>sp[y]) ans+=size[c[y][0]]+1,y=c[y][1]; else y=c[y][0]; return ans+1; } int num(int x) {//排名第x的元素 int y=root; while(x) if(size[c[y][0]]+1<x) x-=size[c[y][0]]+1,y=c[y][1]; else if(size[c[y][0]]+1==x) return sp[y]; else y=c[y][0]; return sp[y]; } int pre(int x) {//输出前驱 int ans; for(int y=root; y;) if(sp[y]<x) ans=sp[y],y=c[y][1]; else y=c[y][0]; return ans; } int nex(int x) {//输出后驱 int ans; for(int y=root; y;) if(sp[y]<=x) y=c[y][1]; else ans=sp[y],y=c[y][0]; return ans; } int main() { scanf("%d",&n); for(int i=1; i<=n; i++) { scanf("%d%d",&p,&q); if(p==1) insert(q); if(p==2) del(q); if(p==3) printf("%d ",rank(q)); if(p==4) printf("%d ",num(q)); if(p==5) printf("%d ",pre(q)); if(p==6) printf("%d ",nex(q)); } return 0; }