平衡树Splay

  1 #include <bits/stdc++.h>
  2 #define root e[0].son[1]
  3 using namespace std;
  4 int read() {
  5     int re = 0, f = 1;
  6     char ch = getchar();
  7     while (ch < ‘0‘ || ch > ‘9‘) {if (ch == ‘-‘) f = -f; ch = getchar();}
  8     while (‘0‘ <= ch && ch <= ‘9‘) {re = re * 10  + ch - ‘0‘; ch = getchar();}
  9     return re * f;
 10 }
 11 const int N = 1e5 + 3;
 12 const int INF = 1e7 + 3;
 13 int n, cnt;
 14 struct node{
 15     int v, father;//储存键值，父亲节点 
 16     int son[2];//存储左右孩子，son[0]为左，son[1]为右 
 17     int sum;//存储这个节点子树共有多少 元素 (元素包括sum + recy) 
 18     int recy;//存储相同键值重复多少次 
 19 }e[N];
 20 void update(int x) {//合并 
 21     e[x].sum = e[e[x].son[0]].sum + e[e[x].son[1]].sum + e[x].recy;
 22 }
 23 int identify(int x) {//确定当前节点与父亲节点的关系 
 24     return e[e[x].father].son[0] == x ? 0 : 1;
 25 }
 26 void connect(int x, int fa, int son) {//连接两个节点 
 27     e[x].father = fa;
 28     e[fa].son[son] = x;
 29 }
 30 void rotate(int x) {//核心函数之一，旋转 
 31     int y = e[x].father;
 32     int mroot = e[y].father;
 33     int mrootson = identify(y);
 34     int yson = identify(x);
 35     int B = e[x].son[yson ^ 1];
 36     connect(B, y, yson); 
 37     connect(y, x, (yson ^ 1));
 38     connect(x, mroot, mrootson);
 39     update(y);//y在上，先更新y 
 40     update(x);
 41 }
 42 void splay(int at, int to) {//核心函数 
 43     to = e[to].father;
 44     while (e[at].father != to) {
 45         int up = e[at].father;
 46         if (e[up].father == to) {
 47             rotate(at);
 48         } else if (identify(at) == identify(up)) {//当自己的父亲与爷爷在一条直线上时，先旋转父亲 
 49             rotate(up);
 50             rotate(at);
 51         } else {//不在同一直线上就旋转两次 
 52             rotate(at);
 53             rotate(at);
 54         }
 55     }
 56 }
 57 int newpoint(int v, int fa) {//添加新节点 
 58     e[++cnt].father = fa;
 59     e[cnt].v = v;
 60     e[cnt].sum = e[cnt].recy = 1;
 61     return cnt;
 62 }
 63 void Insert(int x) {
 64     int now = root;
 65     if(!root){//特判没根的情况 
 66         newpoint(x, 0);
 67         root = cnt;
 68     } else {
 69         while (true) {
 70             e[now].sum++;//经过的点子树中元素都要++ 
 71             if (e[now].v == x) {
 72                 e[now].recy++;//重复 
 73                 splay(now, root);
 74                 return;
 75             }
 76             int next = x < e[now].v ? 0 : 1;//判断该走左孩子还是右孩子 
 77             if (!e[now].son[next]) {
 78                 int add = newpoint(x, now);
 79                 e[now].son[next] = add;
 80                 splay(add, root);
 81                 return;
 82             }
 83             now = e[now].son[next];
 84         }
 85     }
 86 }
 87 int find(int v) {//查询键值为v的点的位置 
 88     int now = root;
 89     while (true) {
 90         if (e[now].v == v) {
 91             splay(now, root);//划重点，下面有用 
 92             return now;
 93         }
 94         int next = v < e[now].v ? 0 : 1;
 95         if (!e[now].son[next]) {
 96             return 0;
 97         }
 98         now = e[now].son[next];
 99     }
100 }
101 void delet(int x) {//删除节点 
102     int now = find(x);//注意find()函数中已经将x转为根节点 
103     if (!now) {
104         return;
105     }
106     if (e[now].recy > 1) {//如果有重复，直接减去即可 
107         e[now].recy--;
108         e[now].sum--;
109     } else {
110         if (!e[now].son[0] && !e[now].son[1]) {//如果没有左右孩子，说明就一个点 
111             root = 0;
112         } else if (!e[now].son[0]) {//如果没有左孩子，直接将右孩子提为根节点 
113             root = e[now].son[1];
114             e[root].father = 0;
115         } else {//左右孩子都有，先将左子树中最大的节点转到左孩子的位置，然后提为根节点，把右孩子连到该节点之下 
116             int lef = e[now].son[0];
117             while (e[lef].son[1]) {//找左子树中最大的节点 
118                 lef = e[lef].son[1];
119             }
120             splay(lef, e[now].son[0]);
121             connect(e[now].son[1], lef, 1);
122             connect(lef, 0, 1);
123             update(lef);
124         }
125     }
126 }
127 int _rank(int v) {
128     int now = find(v);//因为find()已经将v转为根节点，所以直接求即可 
129     return e[e[now].son[0]].sum + 1;
130 }
131 int arank(int x) {
132     int now = root;
133     while (true) {
134         int used = e[now].sum - e[e[now].son[1]].sum;
135         //如果x大于左子树元素，并且小于等于当前点的左子树的sum加上本节点的recy的值，那么当前的点就是要找的点 
136         //因为此时说明该x是当前节点重复值中的一个 
137         if (e[e[now].son[0]].sum < x && x <= used) {
138             splay(now, root);
139             return e[now].v;
140         }
141         if (x < used) {//小于则向左子树寻找 
142             now = e[now].son[0];
143         } else {//大于则减去该值，再向右子树寻找 
144             x -= used;
145             now = e[now].son[1];
146         }
147     }
148 }
149 int lower(int v) {//前驱 
150     int now = root;
151     int ans = -INF;
152     while (now) {
153         if (e[now].v < v && e[now].v > ans) {
154             ans = e[now].v;
155         }
156         if (v > e[now].v) {
157             now = e[now].son[1];
158         } else {
159             now = e[now].son[0];
160         }
161     }
162     return ans;
163 }
164 int upper(int v) {//后继 
165     int now = root;
166     int ans = INF;
167     while(now) {
168         if (e[now].v > v && e[now].v < ans) {
169             ans = e[now].v;
170         }
171         if (v < e[now].v) {
172             now = e[now].son[0];
173         } else {
174             now = e[now].son[1];
175         } 
176     }
177     return ans;
178 }
179 int main () {
180     n = read();
181     while (n--) {
182         int o = read();
183         int x = read();
184         if (o == 1) {
185             Insert(x);
186         } else if (o == 2) {
187             delet(x);
188         } else if (o == 3) {
189             printf("%d\n", _rank(x));
190         } else if (o == 4) {
191             printf("%d\n", arank(x));
192         } else if (o == 5) {
193             printf("%d\n", lower(x));
194         } else if (o == 6) {
195             printf("%d\n", upper(x));
196         }
197     }
198     return 0;
199 }