Hihocoder 1325 （splay）

Problem 平衡树 Treap

题目大意

　　维护一个数列，支持两种操作。

　　操作1：添加一个数x。

　　操作2：询问不超过x的最大的数。

解题分析

　　尝试了一下用指针来写splay，感觉写起来还是比较流畅的，不过用指针的时候还是需要注意一些小细节，要防止对空指针进行赋值。

　　之后继续把指针版splay的各种功能补齐吧，最后写成模板的形式，方便以后使用。（= =树套树的话是不是只能用模板的形式叻。）

　　ps：感觉已经好久没有写博文了，应该是我太懒了吧，还是应该每天写写题，发发博文也算是对自己的一种激励吧，也能把一些心得体会记下来。立个flag：以后每天发一篇博文。

参考程序

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 
  4 struct node{
  5     int val;
  6     node *left,*right,*father;
  7     node(int val_=0,node* father_=NULL,node* left_=NULL,node* right_=NULL)
  8     {
  9         val=val_; father=father_; left=left_; right=right_;
 10     }
 11 }*rt;
 12 
 13 void search(node *now)
 14 {
 15     cout<<now<<" "<<now->val<<" "<<now->left<<" "<<now->right<<" "<<now->father<<endl;
 16     if (now->left) search(now->left);
 17     if (now->right) search(now->right);
 18 }
 19 
 20 void pushup(node *x)
 21 {
 22 }
 23 
 24 void right(node* x,node* &rt)
 25 {
 26     node *y=x->father,*z=y->father;
 27     if (y==rt) rt=x; 
 28     else if (z->left==y) z->left=x; else z->right=x; //需要判断是左右孩子
 29     x->father=z; y->father=x; if (x->right) x->right->father=y;  //防止对空指针进行操作
 30     y->left=x->right; x->right=y; 
 31     pushup(y); pushup(x);
 32 }
 33 
 34 void left(node* x,node* &rt)
 35 {
 36     node *y=x->father,*z=y->father;
 37     if (y==rt) rt=x; 
 38     else if (z->left==y) z->left=x; else z->right=x;  
 39     x->father=z; y->father=x; if (x->left) x->left->father=y;  
 40     y->right=x->left; x->left=y; 
 41     pushup(y); pushup(x);
 42 }
 43 
 44 void splay(node* x,node* &rt)
 45 {
 46     while (x!=rt)
 47     {
 48         node *y=x->father, *z=y->father;
 49         if (z==NULL)
 50         {
 51             if (x==y->left) right(x,rt); 
 52             else left(x,rt);
 53         }
 54         else
 55         {
 56             if (y==z->left)
 57                 if (x==y->left) { right(y,rt); right(x,rt); }
 58                 else { left(x,rt); right(x,rt); }
 59             else
 60                 if (x==y->right) { left(y,rt); left(x,rt); }
 61                 else { right(x,rt); left(x,rt); }
 62         }
 63     }
 64 }
 65 
 66 void insert(int val,node* &now,node *last)
 67 {
 68     if (now==NULL)
 69     {
 70         now=new node(val,last);
 71         splay(now,rt);
 72         return;
 73     }
 74     if (val < now->val) insert(val,now->left,now);  else  //else还是要加的 返回的时候树的形态已经改变了
 75     if (val > now->val) insert(val,now->right,now); else
 76     if (val == now->val) return;
 77 }
 78 
 79 int find(int val,node *x)
 80 {
 81     int res=-1<<30;
 82     while (x!=NULL)
 83     {
 84         if (x->val>val) x=x->left;
 85         else
 86         {
 87             res=max(res,x->val);
 88             x=x->right;
 89         }
 90     }
 91     return res;
 92 
 93 }
 94 
 95 int main()
 96 {
 97     int n;
 98     rt=NULL;
 99     scanf("%d",&n);
100     for (int i=1;i<=n;i++)
101     {
102         char s[3]; int x;
103         scanf("%s%d",s,&x);
104         if (s[0]=='I') insert(x,rt,NULL); else cout<<find(x,rt)<<endl;
105     }
106 }

View Code