Scapegoat Tree 替罪羊树
一种有趣的暴力重构思想 SBT。
学习链接
https://zhuanlan.zhihu.com/p/21263304
例题链接
https://www.luogu.org/problemnew/show/P3369
主要思想
若子树不平衡,则 $O(n)$ 暴力重构。
均摊复杂度 $O(n\log n)$,期望复杂度较为优秀。
在指针的实现上有一些细节(比如用到了指针指指针等),所以说只是应用思想的话可能考场上会 WA 飞
所以还是搞了个模板...
UPD: 2018-11-9
更新了模板,修正了几个错误。
- 替罪羊树不能使用普通的递归前驱后继(会导致复杂度不正确),需要用 Rank 和 kth 来代替。
- 删除的结点个数如果超过树的结点个数的一半则直接暴力重构。
Code
// Code by ajcxsu
// Problem: baltree
#include<bits/stdc++.h>
using namespace std;
template<typename T> inline void gn(T &x) {
char ch=getchar(), pl=0; x=0;
while(ch<'0' || ch>'9') pl=(ch=='-'), ch=getchar();
while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar(); x*=pl?-1:1;
}
const int N=1e5+10;
const double alpha=0.75;
struct Node *nil;
struct Node {
Node *ch[2];
int val, s, c;
Node(int val=-0x3f3f3f3f):val(val) { s=c=1; ch[0]=ch[1]=nil; }
int cmp(int x) { return x==val?-1:x>val; }
void upd() { s=c+ch[0]->s+ch[1]->s; }
bool bad() { return ch[0]->s>s*alpha+3 || ch[1]->s>s*alpha+3; }
} *rt, **bad;
int deled, tot;
void ini() { nil=new Node(), nil->ch[0]=nil->ch[1]=nil, nil->s=nil->c=0; bad=&nil, rt=nil; }
Node *stk[N]; int t;
void re1(Node *x) {
if(x==nil) return;
re1(x->ch[0]);
if(x->c) stk[++t]=x;
re1(x->ch[1]);
if(!x->c) delete x;
}
Node *re2(int l, int r) {
if(l==r) { stk[l]->ch[0]=stk[l]->ch[1]=nil; stk[l]->upd(); return stk[l]; }
else if(l>r) return nil;
int mid=(l+r)>>1;
stk[mid]->ch[0]=re2(l, mid-1), stk[mid]->ch[1]=re2(mid+1, r);
stk[mid]->upd(); return stk[mid];
}
void rebuild() {
if(deled*2>tot) bad=&rt, tot-=deled, deled=0;
if(bad!=&nil) re1(*bad), *bad=re2(1, t), bad=&nil, t=0;
}
void ins(Node *&x, int val) {
if(x==nil) x=new Node(val);
else {
if(x->val==val) x->c++;
else ins(x->ch[x->cmp(val)], val);
}
if(x->bad()) bad=&x;
x->upd();
}
void del(Node *&x, int val) {
int d=x->cmp(val);
if(d==-1) x->c--;
else del(x->ch[d], val);
if(x->bad()) bad=&x;
x->upd();
}
int Rank(Node *x, int k) {
if(x==nil) return 1;
int d=x->cmp(k);
if(d==-1) return x->ch[0]->s+1;
else if(!d) return Rank(x->ch[0], k);
else return Rank(x->ch[1], k)+x->ch[0]->s+x->c;
}
int kth(Node *x, int k) {
if(k<=x->ch[0]->s) return kth(x->ch[0], k);
else if(k<=x->ch[0]->s+x->c) return x->val;
else return kth(x->ch[1], k-x->ch[0]->s-x->c);
}
int main() {
ini();
int q, opt, x;
gn(q);
while(q--) {
gn(opt), gn(x);
if(opt==1) ins(rt, x), tot++, rebuild();
else if(opt==2) del(rt, x), deled++, rebuild();
else if(opt==3) printf("%d\n", Rank(rt, x));
else if(opt==4) printf("%d\n", kth(rt, x));
else if(opt==5) printf("%d\n", kth(rt, Rank(rt, x)-1));
else if(opt==6) printf("%d\n", kth(rt, Rank(rt, x+1)));
}
return 0;
}
本文链接:https://pst.iorinn.moe/archives/scapegoat_tree.html
许可: https://pst.iorinn.moe/license.html若无特别说明,博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆