普通平衡树模板题,这里我写的是 Treap 。
Treap 大概是最最最基本的平衡树了吧(基本上就是 BST 上加了个堆性质)
关于 Treap 的坑点:
- 哪里都不能丢的 update :只要你的操作涉及父子关系的修改,就不要忘记更新子树大小。
- 代码简化:用 \(son[i][0/1]\) 存储左右儿子而非 \(ls[i]\) 和 \(rs[i]\) (对旋转操作的简化显著)。
- 维护堆性质:修改父子关系时,一定要保证以随机权值为关键字的堆性质。
- 细节:各种细节,每一个都可能大大加长你的调试时间(本蒻蒻因少写一个 update 调了一天QAQ)。
具体实现就见代码了吧:(说实话这类数据结构画出图来非常生动形象,就是代码难写)
#include <bits/stdc++.h>
#define Rei register int
#define ll long long
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 1e5+5;
template<typename T>
inline void read(T &x) {
x = 0;
char f = 0, c = getchar();
while(!isdigit(c)) f |= (c=='-'), c = getchar();
if(f) while(isdigit(c)) x = x*10-c+48, c = getchar();
else while(isdigit(c)) x = x*10+c-48, c = getchar();
}
int n;
struct treap {
int tot, root;
int val[N], QAQ[N], cnt[N], size[N];
int son[N][2];
int new_node(int v) {
val[++tot] = v, cnt[tot] = size[tot] = 1, QAQ[tot] = rand();
return tot;
}
void update(int p) {
size[p] = size[son[p][0]] + size[son[p][1]] + cnt[p];
}
void rotate(int &p, int wh) {
int q = son[p][wh];
son[p][wh] = son[q][wh^1], son[q][wh^1] = p, p = q;
update(son[p][wh^1]), update(p);
}
void insert(int &p, int v) {
if(p == 0) {
p = new_node(v);
return;
}
if(v == val[p]) {
++cnt[p], update(p);
return;
}
int wh = v > val[p];
insert(son[p][wh], v);
QAQ[son[p][wh]] > QAQ[p]? rotate(p, wh):update(p);
}
void remove(int &p, int v) {
if(!p) return;
if(v == val[p]) {
if(cnt[p]>1) --cnt[p], update(p);
else if(!son[p][0] && !son[p][1]) p = 0;
else {
if(!son[p][1] || QAQ[son[p][0]] > QAQ[son[p][1]]) rotate(p, 0), remove(son[p][1], v);
else rotate(p, 1), remove(son[p][0], v);
update(p);
}
return;
}
int wh = v > val[p];
remove(son[p][wh], v);
update(p);
}
int get_rank(int p, int v) {
if(v == val[p]) return size[son[p][0]] + 1;
if(v < val[p]) return get_rank(son[p][0], v);
return size[son[p][0]] + cnt[p] + get_rank(son[p][1], v);
}
int get_val(int p, int rank) {
if(size[son[p][0]] + 1 > rank) return get_val(son[p][0], rank);
if(size[son[p][0]] + cnt[p] >= rank) return val[p];
return get_val(son[p][1], rank - size[son[p][0]] - cnt[p]);
}
int get_qian(int v) {
int p = root, ans;
while(p) {
if(val[p] < v) ans = val[p], p = son[p][1];
else p = son[p][0];
}
return ans;
}
int get_hou(int v) {
int p = root, ans;
while(p) {
if(val[p] > v) ans = val[p], p = son[p][0];
else p = son[p][1];
}
return ans;
}
} phs;
int main() {
srand(time(0));
read(n);
int opt, x;
for(Rei i = 1; i <= n; ++i) {
read(opt), read(x);
switch(opt) {
case 1: phs.insert(phs.root, x); break;
case 2: phs.remove(phs.root, x); break;
case 3: printf("%d\n", phs.get_rank(phs.root, x)); break;
case 4: printf("%d\n", phs.get_val(phs.root, x)); break;
case 5: printf("%d\n", phs.get_qian(x)); break;
case 6: printf("%d\n", phs.get_hou(x)); break;
}
}
return 0;
}
希望能对你有帮助!(*/ω\*)