平衡樹的入門題目，也可以用Treap來實現(xiàn)，我覺得Treap的核心就是那個rand()了用來保證樹不退化成鏈，同時還是有平衡樹的特性。?？傮w來說我覺得比較好些，而且比較快

#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <cctype> #include <iostream> using namespace std; const int MAXN = 500000; struct node{int r, v, sz, number;node *ch[2];void rz(){sz = ch[0]->sz + ch[1]->sz + number;} }Edges[MAXN+10], *ecnt = Edges, Tnull, *nil = &Tnull; node *newnode(node *lch, node *rch, int v, int r){++ecnt;ecnt->ch[0] = lch;ecnt->ch[1] = rch;ecnt->v = v;ecnt->r = r;return ecnt; } node *retu; int ret; struct Treap{node *root;Treap(){root = nil; nil->ch[0] = nil->ch[1] = nil;}void rotate(node *&n, bool d){node *a = n->ch[d];n->ch[d] = a->ch[!d]; n->rz();a->ch[!d] = n; a->rz();n = a;}void Insert(node *&rt, int val){if(rt == nil){rt = newnode(nil, nil, val, rand());rt->number = 1;rt->rz();return ;}rt->sz++;if(val == rt->v){rt->number++;}else if(val < rt->v){Insert(rt->ch[0], val);if(rt->ch[0]->r < rt->r)rotate(rt, false);}else if(val > rt->v){Insert(rt->ch[1], val);if(rt->ch[1]->r < rt->r)rotate(rt, true);}}void del(node *&rt, int val){if(rt == nil) return ;rt->sz--;if(rt->v == val){if(rt->number > 1){rt->number--;}else if(rt->ch[0] == nil || rt->ch[1] == nil){if(rt->ch[0]!=nil)rt = rt->ch[0];elsert = rt->ch[1];}else{if(rt->ch[0]->r > rt->ch[1]->r){rotate(rt, false);del(rt->ch[1], val);rt->rz();}else{rotate(rt, true);del(rt->ch[0], val);rt->rz();}}}else if(val < rt->v)del(rt->ch[0], val);elsedel(rt->ch[1], val);}int Rank(node *rt, int val){if(rt == nil) return ret+1;if(rt->v == val)return ret+rt->ch[0]->sz+1;if(val < rt->v)return Rank(rt->ch[0], val);ret += rt->ch[0]->sz+rt->number;return Rank(rt->ch[1], val);}void pre(node *rt, int val){if(rt == nil) return ;else if(rt->v <= val){retu = rt;pre(rt->ch[1], val);}elsepre(rt->ch[0], val);}void bak(node *rt, int val){if(rt == nil) return ;else if(rt->v >= val){retu = rt;bak(rt->ch[0], val);}elsebak(rt->ch[1], val);}int order(node *rt, int rk){if(rt->sz < rk) return 0;if(rk <= rt->ch[0]->sz)return order(rt->ch[0], rk);else if(rk > rt->ch[0]->sz+rt->number)return order(rt->ch[1], rk-rt->ch[0]->sz-rt->number);return rt->v;} }tp; int main(){//freopen("data10.in", "r", stdin);int n;scanf("%d", &n);for(int i=0;i<n;i++){int o, x;scanf("%d %d", &o, &x);switch(o){case 1: tp.Insert(tp.root, x); break;case 2: tp.del(tp.root, x); break;case 3: ret = 0; printf("%d\n", tp.Rank(tp.root, x)); break;case 4: printf("%d\n", tp.order(tp.root, x)); break;case 5: retu = nil;tp.pre(tp.root, x-1); printf("%d\n", retu->v); break;case 6: retu = nil;tp.bak(tp.root, x+1); printf("%d\n", retu->v); break;}}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/JeremyGJY/p/5921723.html

總結(jié)

以上是生活随笔為你收集整理的【Treap】[BZOJ 3224]Tyvj 1728 普通平衡树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。