旋转Treap/Splay模板
这两天又种了两棵平衡树,分别是 Treap 和 Splay。
【旋转 Treap】
模板题:BZOJ 3224
Treap = Tree + Heap,中文名叫树堆,是一种基于随机化的二叉排序树。
普通的二叉排序树在递增或递减的输入下会退化成为一条链,最坏复杂度达 O(n)。
所以我们给每个节点额外赋一个随机值,保持该值满足堆的性质。
就可以达到单次期望 O(logn) 的效果,且不易退化。
旋转 Treap 的思想就是用不破坏中序遍历的旋转操作来维护堆的性质。
注意,为了处理方便,我们将相同的值储存在同一节点内,记录个数即可。
常数似乎较宗法树更大一些。
Code: O(nlogn) [5980K, 532MS]
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std; const int MAXN = 100002; inline void getint(int &num){ char ch; bool neg = 0; while(!isdigit(ch = getchar())) if(ch == '-') neg = 1; num = ch - '0'; while(isdigit(ch = getchar())) num = num * 10 + ch - '0'; if(neg) num = -num; } int n, opt, x; struct Node{ #define sz(x) ((x) ? (x)->size : 0) int val, pri, cnt, size; Node *lc, *rc; Node() {} Node(int v, int c, int s, Node *l, Node *r): val(v), cnt(c), size(s), lc(l), rc(r) {} inline void update() {size = sz(lc) + sz(rc) + cnt;} } pool[MAXN << 1]; inline Node* newNode(int v, int c, int s, Node *l, Node *r){ static int topp = 0; pool[topp] = Node(v, c, s, l, r); return &pool[topp++]; } inline void rotate(Node *&cur, int dir){ if(dir == 0){ Node *o = cur->lc; cur->lc = o->rc, o->rc = cur; o->size = cur->size, cur->update(), cur = o; } else{ Node *o = cur->rc; cur->rc = o->lc, o->lc = cur; o->size = cur->size, cur->update(), cur = o; } } inline void insert(Node *&cur, int v){ if(cur == NULL) cur = newNode(v, 1, 1, NULL, NULL); else{ cur->size++; if(v == cur->val) cur->cnt++; else if(v > cur->val){ insert(cur->rc, v); if(cur->rc->pri < cur->pri) rotate(cur, 1); } else{ insert(cur->lc, v); if(cur->lc->pri < cur->pri) rotate(cur, 0); } } } inline void erase(Node *&cur, int v){ if(cur == NULL) return; if(v == cur->val){ if(cur->cnt > 1) cur->cnt--, cur->size--; else{ if(cur->lc && cur->rc){ if(cur->lc->pri < cur->rc->pri) rotate(cur, 0), erase(cur, v); else rotate(cur, 1), erase(cur, v); // 直接 "erase(cur->lc, v)" 会导致 size 没有更新 !!! } else cur = cur->lc ? cur->lc : cur->rc; } } else{ cur->size--; if(v > cur->val) erase(cur->rc, v); else erase(cur->lc, v); } } inline int rnk(Node *cur, int v){ if(cur == NULL) return 1; // 类比 "宗法树" 的 "return 2;" 操作 if(v == cur->val) return sz(cur->lc) + 1; else if(v < cur->val) return rnk(cur->lc, v); else return sz(cur->lc) + cur->cnt + rnk(cur->rc, v); } inline int kth(Node *cur, int k){ if(cur == NULL) return 0; if(k <= sz(cur->lc)) return kth(cur->lc, k); else if(k > sz(cur->lc) + cur->cnt) return kth(cur->rc, k - sz(cur->lc) - cur->cnt); else return cur->val; } int main(){ srand(19260817); getint(n); Node *root = NULL; while(n--){ getint(opt), getint(x); if(opt == 1) insert(root, x); else if(opt == 2) erase(root, x); else if(opt == 3) printf("%d\n", rnk(root, x)); else if(opt == 4) printf("%d\n", kth(root, x)); else if(opt == 5) printf("%d\n", kth(root, rnk(root, x) - 1)); else if(opt == 6) printf("%d\n", kth(root, rnk(root, x + 1))); } return 0; }
【Splay】Wikipedia
模板题:BZOJ 3223
Splay 中文名叫伸展树,是一种二叉排序树。
它是处理区间问题的利器,但是相对来说常数比较大。
若将 l - 1 旋转至根节点,r + 1 旋转至根的右节点,那么 r + 1 的左子树即为区间 [l, r]。
Code: O(nlogn) [11064K, 1820MS]
// Splay Tree (Balanced Binary Search Tree) // BZOJ 3223 文艺平衡树 /* rotate(cur, dir): 右旋(dir == 0): 设 cur 的左孩子为 o (1) 将 o 的右子树连在 cur 的左子树上 (2) 将 o 连在 cur 的父亲的左/右子树上 (3) 将 cur 连在 o 的右子树上 左旋(dir == 1): 设 cur 的右孩子为 o (1) 将 o 的左子树连在 cur 的右子树上 (2) 将 o 连在 cur 的父亲的左/右子树上 (3) 将 cur 连在 o 的左子树上 splay(cur, tf): Zig Step: 当 cur 的父节点离目标父节点 tf 只差一层时, 旋转父节点 Zig-zig Step: 若 cur 与其父节点子树情况相同, 先旋转爷爷节点, 再旋转父节点 Zig-zag Step: 若 cur 与其父节点子树情况相反, 旋转父节点不同方向各一次 */ #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std; const int MAXN = 100002; inline void getint(int &num){ char ch; while(!isdigit(ch = getchar())); num = ch - '0'; while(isdigit(ch = getchar())) num = num * 10 + ch - '0'; } int n, m, a[MAXN]; struct Splay_Tree{ struct Node{ #define islc(cur) ((cur) == (cur)->fa->ch[0]) #define isrc(cur) ((cur) == (cur)->fa->ch[1]) int val, size, rev; Node *fa, *ch[2]; Node(): val(0), size(0), rev(0), fa(NULL) {ch[0] = ch[1] = NULL;} Node(int v, int s, Node *f, Node *l, Node *r): val(v), size(s), rev(0), fa(f) {ch[0] = l, ch[1] = r;} inline void update() {size = (ch[0] ? ch[0]->size : 0) + (ch[1] ? ch[1]->size : 0) + 1;} inline void pushdown(){ if(rev){ swap(ch[0], ch[1]); if(ch[0]) ch[0]->rev ^= 1; if(ch[1]) ch[1]->rev ^= 1; rev = 0; } } } pool[MAXN << 2], *root; inline Node* newNode(int v, int s, Node *f, Node *l, Node *r){ static int topp = 0; pool[topp] = Node(v, s, f, l, r); return &pool[topp++]; } inline Node* build(int *sorted, int l, int r, Node *fa = NULL){ int smid = l + r >> 1; Node *cur = newNode(sorted[smid], 0, fa, NULL, NULL); if(l < smid) cur->ch[0] = build(sorted, l, smid - 1, cur); if(smid < r) cur->ch[1] = build(sorted, smid + 1, r, cur); return cur->update(), cur; } inline void rotate(Node *cur, int dir){ Node *o = cur->ch[dir]; if(!o) return; cur->pushdown(), o->pushdown(); cur->ch[dir] = o->ch[dir ^ 1]; if(o->ch[dir ^ 1]) o->ch[dir ^ 1]->fa = cur; o->fa = cur->fa; if(!cur->fa) root = o; else if(islc(cur)) cur->fa->ch[0] = o; else cur->fa->ch[1] = o; o->ch[dir ^ 1] = cur, cur->fa = o; cur->update(), o->update(); } inline void splay(Node *cur, Node *tf){ while(cur->fa != tf){ if(cur->fa->fa == tf) if(islc(cur)) rotate(cur->fa, 0); else rotate(cur->fa, 1); else if(islc(cur) && islc(cur->fa)) rotate(cur->fa->fa, 0), rotate(cur->fa, 0); else if(isrc(cur) && isrc(cur->fa)) rotate(cur->fa->fa, 1), rotate(cur->fa, 1); else if(islc(cur) && isrc(cur->fa)) rotate(cur->fa, 0), rotate(cur->fa, 1); else rotate(cur->fa, 1), rotate(cur->fa, 0); } } inline Node* find(int id){ Node *p = root; while(p){ p->pushdown(); int lsize = p->ch[0] ? p->ch[0]->size + 1 : 1; if(id < lsize) p = p->ch[0]; else if(id > lsize) id -= lsize, p = p->ch[1]; else return p; } return NULL; } inline void reverse(int l, int r){ if(l >= r) return; Node *pl = find(l - 1), *pr = find(r + 1); if(pl && pr) {splay(pl, NULL), splay(pr, pl); if(pr->ch[0]) pr->ch[0]->rev ^= 1;} else if(pr) {splay(pr, NULL); if(pr->ch[0]) pr->ch[0]->rev ^= 1;} else if(pl) {splay(pl, NULL); if(pl->ch[1]) pl->ch[1]->rev ^= 1;} else if(root) root->rev ^= 1; } inline void inorder(Node *cur){ cur->pushdown(); if(cur->ch[0]) inorder(cur->ch[0]); printf("%d ", cur->val); if(cur->ch[1]) inorder(cur->ch[1]); } } splay; int main(){ getint(n), getint(m); for(register int i = 1; i <= n; i++) a[i] = i; splay.root = splay.build(a, 1, n); for(register int i = 1; i <= m; i++){ int l, r; getint(l), getint(r); splay.reverse(l, r); } splay.inorder(splay.root); puts(""); return 0; }
bjz
种树巨爷%%%%%%%%%