替罪羊树模板
突然发现一个月没写 Blog 了，滚回来补锅。。据说要补 30+ 篇 ?!! 就当复习吧。。
替罪羊树 (Scapegoat Tree) 是一棵基于局部重构 (partially rebuild) 的平衡树。
其主要思想是当一棵子树的不平衡程度到达某一阈值时，将该子树拍扁 (flatten) 成中序遍历，然后从中部上拉 (pullup) 成一棵完全二叉树。
由于没有旋转 (rotate) 或者分裂合并 (split & merge) 操作，替罪羊树在删除节点时并不是将节点移除，而是打上标记，在统计时不计入答案即可。我们用 cov[] 表示子树总节点数，sz[] 表示子树真正存在的节点数。
关于上述阈值的选取，对于任意节点作为根节点，均遵循以下规则：
- 当左子树（或右子树）的总节点数大于整棵树总节点数的 α 倍时，认定当前树不平衡，需要重构。其中 α 通常选取 [0.6, 0.8] 区间上的数。
- max(cov[lc[u]], cov[rc[u]]) > cov[u] * α
- 当整棵树中被删除的节点数大于总节点数的一半时，认定当前树冗余信息过多，需要重构。
- sz[u] * 2 < cov[u]
需要注意的是，insert() 的返回值为指向需重构子树的根节点的指针。另外，由于删除标记的影响，erase() 若按值删除则可能无法判断目标在左子树还是右子树内，需要按排名删除。
替罪羊树复杂度可以证明为均摊单次 O(logn)，且常数较 Treap, Splay 等均更优越。其局限性为不支持区间操作，只能实现名次树。
模板题为 BZOJ 3224 普通平衡树。
Code: O(nlogn) [6964K, 324MS]
// 替罪羊树 (2018.3.5)
// BZOJ 3224 普通平衡树
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>
#include<iostream>
#include<algorithm>
#define MAXN 100005
using namespace std;
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;
int root, val[MAXN << 1], sz[MAXN << 1], cov[MAXN << 1], lc[MAXN << 1], rc[MAXN << 1];
bool exi[MAXN << 1];
int fl[MAXN << 1], topfl;
int bin[MAXN << 1], topbin = 0;
inline int newNode(int v, int s, int c, int l, int r){
static int topp = 0;
int u = topbin ? bin[topbin--] : ++topp;
val[u] = v, sz[u] = s, cov[u] = c, lc[u] = l, rc[u] = r, exi[u] = 1;
return u;
}
inline void delNode(int u) {bin[++topbin] = u;}
inline bool balanced(int u) {return max(cov[lc[u]], cov[rc[u]]) <= cov[u] * 0.75 + 5;} // 平衡因子取 0.75
inline void update(int u) {sz[u] = sz[lc[u]] + sz[rc[u]] + exi[u], cov[u] = cov[lc[u]] + cov[rc[u]] + 1;}
inline void flatten(int u){
if(lc[u]) flatten(lc[u]);
if(exi[u]) fl[++topfl] = u; else delNode(u);
if(rc[u]) flatten(rc[u]);
}
inline int pullup(int l, int r){
if(l > r) return 0;
int mid = l + r >> 1, u = fl[mid];
lc[u] = pullup(l, mid - 1), rc[u] = pullup(mid + 1, r);
return update(u), u;
}
inline void rebuild(int &u) {topfl = 0, flatten(u), u = pullup(1, topfl);}
inline int* insert(int &u, int v){
if(!u) return u = newNode(v, 1, 1, 0, 0), (int*)NULL;
else{
sz[u]++, cov[u]++; int *sub;
if(v < val[u]) sub = insert(lc[u], v);
else sub = insert(rc[u], v);
return balanced(u) ? sub : &u;
}
}
//inline void erase(int u, int v){ // Erase with value
// if(!u) return;
// sz[u]--;
// if(exi[u] && v == val[u]) {exi[u] = 0; return;}
// else{
// if(v < val[u]) erase(lc[u], v);
// else erase(rc[u], v);
// }
//}
/* Wrong Answer - Cannot assert whether v is in the left or right subtree when (exi[u] == false && v == val[u]). */
inline void erase(int u, int k){ // Erase with rank
sz[u]--;
if(exi[u] && k == sz[lc[u]] + 1) {exi[u] = 0; return;}
else{
if(k <= sz[lc[u]] + exi[u]) erase(lc[u], k);
else erase(rc[u], k - sz[lc[u]] - exi[u]);
}
}
inline int rnk(int u, int v){
int res = 1;
while(u){
if(v <= val[u]) u = lc[u];
else res += sz[lc[u]] + exi[u], u = rc[u];
}
return res;
}
inline int kth(int u, int k){
while(u){
if(exi[u] && k == sz[lc[u]] + 1) return val[u];
if(k <= sz[lc[u]]) u = lc[u];
else k -= sz[lc[u]] + exi[u], u = rc[u];
}
}
int main(){
getint(n);
for(register int i = 1; i <= n; i++){
getint(opt), getint(x);
if(opt == 1){
int *p = insert(root, x);
if(p) rebuild(*p);
}
else if(opt == 2){
erase(root, rnk(root, x));
if(sz[root] * 2 < cov[root]) rebuild(root);
}
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;
}