替罪羊树模板
Code（指针版）：
#include <bits/stdc++.h> using namespace std; typedef long long ll; bool Finish_read; template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;} template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x+'0');} template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');} template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);} /*================Header Template==============*/ const double alpha=0.7; int n; /*==================Define Area================*/ namespace ScapegoatTree { struct node { node *l,*r; int v,sz,valid; bool del; bool Bad() { return (double)l->sz>alpha*(double)sz||(double)r->sz>alpha*(double)sz; } void Update() { sz=!del+l->sz+r->sz; valid=!del+l->valid+r->valid; } }; node *null; void Dfs(node *o,std::vector<node*> &v) { if(o==null) return ; Dfs(o->l,v); if(!o->del) v.push_back(o); Dfs(o->r,v); if(o->del) delete o; } node *Build(std::vector<node*> &v,int l,int r) { if(l>=r) return null; int mid=(l+r)>>1; node *o=v[mid]; o->l=Build(v,l,mid); o->r=Build(v,mid+1,r); o->Update(); return o; } void ReBuild(node* &o) { std::vector<node*>v; Dfs(o,v); o=Build(v,0,v.size()); } void Insert(int x,node* &o) { if(o==null) { o=new node; o->l=o->r=null; o->del=false; o->sz=o->valid=1; o->v=x; return ; } ++o->sz;++o->valid; if(x>=o->v) Insert(x,o->r); else Insert(x,o->l); if(o->Bad()) ReBuild(o); } int GetRank(node* o,int x) { int ans=1; while(o!=null) { if(o->v>=x) o=o->l; else { ans+=o->l->valid+!o->del; o=o->r; } } return ans; } int FindKth(node* o,int x) { while(o!=null) { if(!o->del&&o->l->valid+1==x) return o->v; if(o->l->valid>=x) o=o->l; else { x-=o->l->valid+!o->del; o=o->r; } } } void Delete(node *o,int rnk) { if(!o->del&&rnk==o->l->valid+1) { o->del=1; --o->valid; return ; } --o->valid; if(rnk<=o->l->valid+!o->del) Delete(o->l,rnk); else Delete(o->r,rnk-o->l->valid-!o->del); } node *rt; } using namespace ScapegoatTree; int main() { null=new node; rt=null; read(n); while(n--) { int opt,x; read(opt);read(x); if(opt==1) Insert(x,rt); if(opt==2) Delete(rt,GetRank(rt,x)); if(opt==3) writeln(GetRank(rt,x)); if(opt==4) writeln(FindKth(rt,x)); if(opt==5) writeln(FindKth(rt,GetRank(rt,x)-1)); if(opt==6) writeln(FindKth(rt,GetRank(rt,x+1))); } return 0; }Code（数组版）：
#include <bits/stdc++.h> using namespace std; typedef long long ll; bool Finish_read; template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;} template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x+'0');} template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');} template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);} /*================Header Template==============*/ #define PAUSE printf("Press Enter key to continue..."); fgetc(stdin); const double alpha=0.7; const int N=1e5+500; int n; /*==================Define Area================*/ namespace ScapegoatTree { struct node { int l,r,v,sz,valid; bool del; void New(int x) {l=r=0;v=x;sz=valid=1;del=0;} }t[N<<2]; #define ls(o) t[o].l #define rs(o) t[o].r #define pb push_back int tot=0,rt=0; bool Bad(int o) { return (double)t[ls(o)].sz>alpha*t[o].sz||(double)t[rs(o)].sz>alpha*t[o].sz; } void Updata(int o) { t[o].sz=t[ls(o)].sz+t[rs(o)].sz+!t[o].del; t[o].valid=t[ls(o)].valid+t[rs(o)].valid+!t[o].del; } void Dfs(int o,std::vector<int> &v) { if(!o) return ; Dfs(ls(o),v); if(!t[o].del) v.pb(o); Dfs(rs(o),v); return ; } int Build(std::vector<int> &v,int l,int r) { if(l>=r) return 0; int mid=(l+r)>>1; int o=v[mid]; ls(o)=Build(v,l,mid); rs(o)=Build(v,mid+1,r); Updata(o); return o; } void ReBuild(int &o) { std::vector<int>v; Dfs(o,v); o=Build(v,0,(int)v.size()); } void Insert(int x,int &o) { if(!o) { o=++tot; t[o].New(x); return ; } t[o].sz++;t[o].valid++; if(x>=t[o].v) Insert(x,rs(o)); else Insert(x,ls(o)); if(Bad(o)) ReBuild(o); return ; } int GetRank(int o,int x) { int ans=1; while(o) { if(t[o].v>=x) o=ls(o); else { ans+=t[ls(o)].valid+!t[o].del; o=rs(o); } } return ans; } int FindKth(int o,int x) { while(o) { if(!t[o].del&&t[ls(o)].valid+1==x) {return t[o].v;} if(t[ls(o)].valid>=x) o=ls(o); else { x-=t[ls(o)].valid+!t[o].del; o=rs(o); } } } void Delete(int o,int Rnk) { if(!t[o].del&&Rnk==t[ls(o)].valid+1) { t[o].del=1; --t[o].valid; return ; } --t[o].valid; if(Rnk<=t[ls(o)].valid+!t[o].del) Delete(ls(o),Rnk); else Delete(rs(o),Rnk-t[ls(o)].valid-!t[o].del); } } using namespace ScapegoatTree; int main() { read(n); rt=0; while(n--) { int opt,x; read(opt);read(x); if(opt==1) Insert(x,rt); if(opt==2) Delete(rt,GetRank(rt,x)); if(opt==3) writeln(GetRank(rt,x)); if(opt==4) writeln(FindKth(rt,x)); if(opt==5) writeln(FindKth(rt,GetRank(rt,x)-1)); if(opt==6) writeln(FindKth(rt,GetRank(rt,x+1))); } return 0; }转载于:https://www.cnblogs.com/Apocrypha/p/9430699.html
相关资源：JAVA上百实例源码以及开源项目