【模板】替罪羊树

本文主要是介绍【模板】替罪羊树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本来是打开了一道点分治的题，后来发现要用高速平衡树
据说$splay$和$fhqTreap$都非常非常的慢
据说替罪羊树是除了红黑树以外最快的平衡树？
于是就来学习了一下

核心思想就是每次插入不改变树的形态，当树极不平衡时就把它拍扁重构
这里设$alpha=0.8$好像最快

（还有那道点分治也没有写 数据结构什么的太毒了

模板题：luoguP3369 【模板】普通平衡树

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define N 100005
#define LL long long
using namespace std;template<class T>inline void rd(T &x){x=0; short f=1; char c=getchar();while(c<'0' || c>'9') f=c=='-'?-1:1,c=getchar();while(c<='9' && c>='0') x=x*10+c-'0',c=getchar();x*=f;
}const double alpha=0.8;int memory[N],cur[N],m;
int rt,pool,poi,cnt,to_rb;
int ch[N][2],val[N],siz[N],tot[N];//siz is real
bool ban[N];inline bool isbad(int x){if(1.0*siz[x]*alpha<=(double)max(siz[ch[x][0]],siz[ch[x][1]])) return true;return false;
}void dfs(int x){//拍扁if(!x) return; dfs(ch[x][0]);if(!ban[x]) cur[++poi]=x;else memory[++pool]=x;dfs(ch[x][1]);
}void build(int &x,int l,int r){//重构int mid=l+r>>1; x=cur[mid];if(l==r){ch[x][0]=ch[x][1]=0;siz[x]=tot[x]=1;return;}if(l<mid) build(ch[x][0],l,mid-1);else ch[x][0]=0;build(ch[x][1],mid+1,r);tot[x]=tot[ch[x][0]]+tot[ch[x][1]]+1;siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;
}inline void rebuild(int &x){poi=0; dfs(x);if(poi) build(x,1,poi);else x=0;
}void insert(int &now,int x){if(!now){now=memory[pool--]; val[now]=x;ban[now]=0,tot[now]=siz[now]=1;ch[now][0]=ch[now][1]=0;return;}tot[now]++,siz[now]++;if(val[now]>=x) insert(ch[now][0],x);else insert(ch[now][1],x);bool b=isbad(now);if(!b && to_rb){if(ch[now][0]==to_rb) rebuild(ch[now][0]);else rebuild(ch[now][1]);to_rb=0;}else if(b) to_rb=now;
}inline int get_rk(int x){int now=rt,ret=1;while(now){if(val[now]>=x) now=ch[now][0];else{ret+=siz[ch[now][0]]+(!ban[now]);now=ch[now][1];}} return ret;
}inline int get_kth(int x){int now=rt;while(now){if(!ban[now] && siz[ch[now][0]]+1==x) return val[now];else if(siz[ch[now][0]]>=x) now=ch[now][0];else x-=siz[ch[now][0]]+(!ban[now]),now=ch[now][1];}
}void del_pos(int &now,int x){if(!ban[now] && siz[ch[now][0]]+1==x){ban[now]=1; siz[now]--;return;}siz[now]--;if(siz[ch[now][0]]+(!ban[now])>=x) del_pos(ch[now][0],x);else del_pos(ch[now][1],x-siz[ch[now][0]]-(!ban[now]));
}void del_val(int x){del_pos(rt,get_rk(x));if(1.0*tot[rt]*alpha>siz[rt]) rebuild(rt);
}int main(){for(int i=100000;i;i--) memory[++pool]=i;rd(m); int opt,x;while(m--){rd(opt),rd(x);if(opt==1){insert(rt,x);if(isbad(rt)) rebuild(rt);}if(opt==2) del_val(x);if(opt==3) printf("%d\n",get_rk(x));if(opt==4) printf("%d\n",get_kth(x));if(opt==5) printf("%d\n",get_kth(get_rk(x)-1));if(opt==6) printf("%d\n",get_kth(get_rk(x+1)));}return 0;
}

这篇关于【模板】替罪羊树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---