Hihocoder 1337 (splay)

Problem 平衡树 SBT

题目大意

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

　　操作一：插入一个数。

　　操作二：询问第k小的数。

解题分析

　　~~刷刷水题，再熟悉一下splay的基本操作。

　　ps：哇咔咔，有连续四天的假期了，好开心~~

参考程序

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 struct node{
 5     int v,sz;
 6     node *l,*r,*f;
 7     node(int v_=0,int sz_=0,node* f_=NULL,node* l_=NULL,node* r_=NULL)
 8     {
 9         v=v_; sz=sz_; l=l_; r=r_; f=f_;
10     }
11 }*rt;
12 
13 inline void pushup(node *x)
14 {
15     x->sz=1;
16     if (x->l) x->sz += x->l->sz;
17     if (x->r) x->sz += x->r->sz;
18 }
19 void left(node* x,node* &rt)
20 {
21     node *y=x->f , *z=y->f;
22     if (y==rt) rt=x; else
23         if (y==z->l) z->l=x; else z->r=x;
24     x->f=y->f; y->f=x; if (x->l) x->l->f=y; y->r=x->l; x->l=y;
25     pushup(y); pushup(x); 
26 }
27 void right(node* x,node* &rt)
28 {
29     node *y=x->f , *z=y->f;
30     if (y==rt) rt=x; else
31         if (y==z->l) z->l=x; else z->r=x;
32     x->f=y->f; y->f=x; if (x->r) x->r->f=y; y->l=x->r; x->r=y;
33     pushup(y); pushup(x); 
34 }
35 void splay(node* x,node* &rt)
36 {
37     while (x!=rt)
38     {
39         node *y=x->f , *z=y->f;
40         if (y==rt)
41             if (x == y->l) right(x,rt); else left(x,rt);
42         else
43             if (y == z->l) 
44                 if (x == y->l) {right(y,rt);right(x,rt);}
45                     else {left(x,rt);right(x,rt);}
46             else
47                 if (x == y->r) {left(y,rt);left(x,rt);}
48                     else {right(x,rt);left(x,rt);} 
49     }
50 }
51 
52 void insert(int v,node* &x,node* f)
53 {
54     if (x==NULL)
55     {
56         x=new node(v,1,f);
57         splay(x,rt);
58         return;
59     }
60     if (v < x->v) insert(v,x->l,x); else insert(v,x->r,x);
61 }
62 
63 int query(int k,node *x)
64 {
65     int num=x->l?x->l->sz:0;
66     if (k==num+1) return x->v;
67     if (k<num+1) return query(k,x->l);
68     return query(k-num-1,x->r); 
69 }
70 void search(node *x)
71 {
72     if (x==NULL) return;
73     cout<<x->v<<" "<<x->sz;
74     if (x->l) cout<<" lson:"<<x->l->v;
75     if (x->r) cout<<" rson:"<<x->r->v;
76     cout<<endl;
77     if (x->l) search(x->l);
78     if (x->r) search(x->r);
79 
80 }
81 int main()
82 {
83     int n;
84     rt=NULL;
85     scanf("%d",&n);
86     for (int i=1;i<=n;i++)
87     {
88         //search(rt);
89         char s[3]; int x;
90         scanf("%s%d",s,&x);
91         if (s[0]=='I') insert(x,rt,NULL); else cout<<query(x,rt)<<endl;
92     }
93 }

View Code