很水的splay树。

会简单的操作即可。。。

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        using namespace std; #define maxn 1100000 #define mem(a,b) memset(a,b,sizeof(a)) #define root10 ch[ch[root][1]][0] #define root1 ch[root][1] int size[maxn]; int ch[maxn][2]; int pre[maxn]; int root,tot; int key[maxn]; int val[maxn]; int n; int pos; void Treaval(int x) { if(x) { Treaval(ch[x][0]); printf("结点%2d:左儿子 %2d 右儿子 %2d 父结点 %2d size = %2d ,key = %2d \n",x,ch[x][0],ch[x][1],pre[x],size[x],key[x]); Treaval(ch[x][1]); } } void debug() {printf("root:%d\n",root);Treaval(root);} //以上Debug void init() { } void newnode(int &x,int k,int p,int father) { x=++tot; pre[x]=father; size[x]=1; ch[x][0]=ch[x][1]=0; key[x]=p; val[x]=k; } void push_down(int x) { } void push_up(int x) { } void rot(int x,int kind) { int y=pre[x]; push_down(y); push_down(x); ch[y][!kind]=ch[x][kind]; pre[ch[x][kind]]=y; if(pre[y])ch[pre[y]][ch[pre[y]][1]==y]=x; pre[x]=pre[y]; ch[x][kind]=y; pre[y]=x; push_up(y); push_up(x); } void splay(int x,int goal) { push_down(x); while(pre[x]!=goal) { if(pre[pre[x]]==goal) { push_down(pre[x]); push_down(x); rot(x,ch[pre[x]][0]==x); } else { int y=pre[x]; push_down(pre[y]); push_down(y); push_down(x); int kind=ch[pre[y]][0]==y; if(ch[y][kind]==x) { rot(x,!kind); rot(x,kind); } else { rot(y,kind); rot(x,kind); } } } push_up(x); if(goal==0)root=x; } void insert(int k,int p) { int rt=root; int r=root; while(rt!=0) { r=rt; if(key[rt]