替罪羊树
cpp
namespace ScapegoatTree{
struct Node{
int ls,rs,val,sz,fact;
bool exist;
} tzy[N];
int idx,root;
vector<int> v,mem;// 用于重建
int newNode(int val){
int u;
if(mem.size())u=mem.back(),mem.pop_back();
else u=++idx;
tzy[u]={0,0,val,1,1,1};
return u;
}
void dfs(int u){
if(!u)return;
dfs(tzy[u].ls);
if(tzy[u].exist)v.push_back(u);
else mem.push_back(u);
dfs(tzy[u].rs);
}
void pushup(int u){
tzy[u].sz=tzy[tzy[u].ls].sz+tzy[tzy[u].rs].sz+1;
tzy[u].fact=tzy[tzy[u].ls].fact+tzy[tzy[u].rs].fact+tzy[u].exist;
}
int build(int l,int r){
if(l>r)return 0;
if(l==r){
int u=v[l];
tzy[u].ls=tzy[u].rs=0;
tzy[u].sz=tzy[u].fact=1;
tzy[u].exist=true;
return u;
}
int mid=l+r>>1;
int u=v[mid];
tzy[u].ls=build(l,mid-1);
tzy[u].rs=build(mid+1,r);
pushup(u);
return u;
}
void rebuild(int &u){
v.clear();
dfs(u);
if(v.empty()){
u=0;
return;
}
u=build(0,v.size()-1);
}
bool imbalance(int u){
if(max(tzy[tzy[u].ls].fact,tzy[tzy[u].rs].fact)>=tzy[u].fact*0.75)return true;
return false;
}
void insert(int &u,int val){
if(!u){
u=newNode(val);
return;
}
if(val<tzy[u].val)insert(tzy[u].ls,val);
else insert(tzy[u].rs,val);
pushup(u);
if(imbalance(u))rebuild(u);
}
void erase(int &u,int rk){
if(tzy[u].exist&&rk==tzy[tzy[u].ls].fact+1){
tzy[u].exist=0;
tzy[u].fact--;
return;
}
if(rk<=tzy[tzy[u].ls].fact+tzy[u].exist)erase(tzy[u].ls,rk);
else erase(tzy[u].rs,rk-tzy[tzy[u].ls].fact-tzy[u].exist);
pushup(u);
if(imbalance(u))rebuild(u);
}
int find_rank(int val){
int u=root,ans=1;
while(u){
if(val<=tzy[u].val)u=tzy[u].ls;
else{
ans+=tzy[tzy[u].ls].fact+tzy[u].exist;
u=tzy[u].rs;
}
}
return ans;
}
void erase(int val){
erase(root,find_rank(val));
if(imbalance(root))rebuild(root);
}
int kth(int k){
int u=root;
while(u){
if(tzy[u].exist&&tzy[tzy[u].ls].fact+tzy[u].exist==k)break;
if(k<=tzy[tzy[u].ls].fact)u=tzy[u].ls;
else{
k-=tzy[tzy[u].ls].fact+tzy[u].exist;
u=tzy[u].rs;
}
}
return tzy[u].val;
}
int find_prev(int val){
return kth(find_rank(val)-1);
}
int find_next(int val){
return kth(find_rank(val+1));
}
};