思想解析

本质上就是普通的BST，只是多了一个重建不平衡子树的重构操作。

很显然每个平衡树都有一个维护平衡的操作，那么替罪羊树的平衡操作就是重构。

最开始的时候教练说替罪羊十分暴力，一不平衡整棵树拍扁重构。但是其实并不是整棵树重构，而且操作并不算特别暴力，我个人觉得挺妙的，而且速度比平衡树双子（treap，splay）快。

好那么快速开始。

操作讲解

重构(rbu)

核心操作！开始。

我们对于一个不平衡的子树进行重构，很显然如果我们随随便便就重构是极其低能的，我们要对不平衡进行定义。于是有 $canrbu$ 函数。我们设定一个平衡因子 $alpha$ ,对于一颗子树，如果它的大小乘上 $alpha$ 小于等于左右儿子的子树大小的最大值(这里约定一下，本文的子树大小为树上节点大小，实际大小为树上数的大小)，或者当前子树的实际大小比子树大小乘 $alpha$ 小了，很显然是不平衡的，于是进行重构。

Code:

	inline bool canrbu(int x){
		return t[x].cnt&&(t[x].sz*alpha<=(double)Max(t[lc(x)].sz,t[rc(x)].sz)||(double)t[x].fc<=t[x].sz*alpha);
	}

确定是否需要重构后考虑如何重构。我们可以按中序遍历把子树拍扁，这样得到的序列满足二叉搜索树的性质，然后二分把树再提起来，这样树高就变成 $log$ 的了。需要注意替罪羊的删除操作是惰性删除，只是将计数器减一，所以在重构的时候我们考虑只将计数器不为0的点拍扁，为0就扔掉不要了。

Code:

	void rbu_ldr(int &top,int x){
		if(!x) return;
		rbu_ldr(top,lc(x));
		if(t[x].cnt) fd[top++]=x;
		rbu_ldr(top,rc(x));
	}
	int rbu_build(int l,int r){
		if(l>=r) return 0;
		int mid=(l+r)>>1;
		lc(fd[mid])=rbu_build(l,mid);
		rc(fd[mid])=rbu_build(mid+1,r);
		update(fd[mid]);
		return fd[mid]; 
	}
	inline void rbu(int &x){
		int top=0;
		rbu_ldr(top,x);
		x=rbu_build(0,top);
	}

插入，删除(ins，del)

直接按照二叉搜索树插入即可，只是需要注意，我们每一次操作完需要对子树进行检查，判断子树是否平衡，然后对于有需要的子树重建。

Code:

	void ins(int &x,int k){
		if(!x){
			x=++tot;
			if(!rt) rt=1;
			lc(x)=rc(x)=0;
			t[x].val=k;
			t[x].cnt=t[x].fc=t[x].sz=1;
			return;
		}
		if(k==t[x].val) ++t[x].cnt;
		else if(k<t[x].val) ins(lc(x),k);
		else if(k>t[x].val) ins(rc(x),k);
		update(x);
		if(canrbu(x)) rbu(x);
	}
	void del(int &x,int k){
		if(!x) return;
		if(k==t[x].val){
			if(t[x].cnt) --t[x].cnt;
		}
		else if(k<t[x].val) del(lc(x),k);
		else if(k>t[x].val) del(rc(x),k);
		update(x);
		if(canrbu(x)) rbu(x);
	}

查找第一个小于/大于的数的排名(up_bound,up_great)

小进左，大进右即可。进右子树时把左子树的贡献加上。访问到空节点和找到目标时考虑对于需要进行调整即可。

Code:

	int up_great(int x,int k){
		if(!x) return 0;
		if(k==t[x].val&&t[x].cnt) return t[lc(x)].fc;
		else if(k<t[x].val) return up_great(lc(x),k);
		else return up_great(rc(x),k)+t[lc(x)].fc+t[x].cnt;
	}
	int up_bound(int x,int k){
		if(!x) return 1;
		if(k==t[x].val&&t[x].cnt) return t[lc(x)].fc+t[x].cnt+1;
		else if(k<t[x].val) return up_bound(lc(x),k);
		else return up_bound(rc(x),k)+t[lc(x)].fc+t[x].cnt;
	}

查询排名位k的数(kth)

经典思想，学过权值线段树或者其他平衡树的话不难理解。

Code:

	int kth(int x,int k){
		if(!x) return 0;
		if(t[lc(x)].fc<k&&k<=t[lc(x)].fc+t[x].cnt) return t[x].val;
		else if(t[lc(x)].fc+t[x].cnt<k) return kth(rc(x),k-t[lc(x)].fc-t[x].cnt);
		else return kth(lc(x),k);
	}

查询数的排名以及前驱、后继(rk，pre，nxt)

直接用前面的函数就好了。

	inline int rk(int x,int k){
		return up_great(x,k)+1;
	}
	inline int pre(int x,int k){
		return kth(x,up_great(x,k));
	}
	inline int nxt(int x,int k){
		return kth(x,up_bound(x,k));
	}

喜闻乐见的嫁接

由于替罪羊树本质就是个BST，可以偷别的平衡树的操作过来，那么就可以支持序列维护啦（显然非常舒服）！

既然非旋就非旋到底，我们嫁接 $fhq\ treap$ 的分裂合并过来。要用就直接用就可以了。

结构体封装时间

struct Scapegoat{
	#define lc(x) t[x].lc
	#define rc(x) t[x].rc
	int tot,rt;
	double alpha;
	int fd[N];
	Scapegoat(){
		tot=rt=0;
		alpha=0.7;
	}
	struct Node{
		int lc,rc,cnt;
		int val,fc,sz;
	}t[N];
	inline void update(int x){
		t[x].sz=(t[lc(x)].sz+t[rc(x)].sz+1);
		t[x].fc=(t[lc(x)].fc+t[rc(x)].fc+t[x].cnt);
	}
	inline bool canrbu(int x){
		return t[x].cnt&&(t[x].sz*alpha<=(double)Max(t[lc(x)].sz,t[rc(x)].sz)||(double)t[x].fc<=t[x].sz*alpha);
	}
	void rbu_ldr(int &top,int x){
		if(!x) return;
		rbu_ldr(top,lc(x));
		if(t[x].cnt) fd[top++]=x;
		rbu_ldr(top,rc(x));
	}
	int rbu_build(int l,int r){
		if(l>=r) return 0;
		int mid=(l+r)>>1;
		lc(fd[mid])=rbu_build(l,mid);
		rc(fd[mid])=rbu_build(mid+1,r);
		update(fd[mid]);
		return fd[mid]; 
	}
	inline void rbu(int &x){
		int top=0;
		rbu_ldr(top,x);
		x=rbu_build(0,top);
	}
	void ins(int &x,int k){
		if(!x){
			x=++tot;
			if(!rt) rt=1;
			lc(x)=rc(x)=0;
			t[x].val=k;
			t[x].cnt=t[x].fc=t[x].sz=1;
			return;
		}
		if(k==t[x].val) ++t[x].cnt;
		else if(k<t[x].val) ins(lc(x),k);
		else if(k>t[x].val) ins(rc(x),k);
		update(x);
		if(canrbu(x)) rbu(x);
	}
	void del(int &x,int k){
		if(!x) return;
		if(k==t[x].val){
			if(t[x].cnt) --t[x].cnt;
		}
		else if(k<t[x].val) del(lc(x),k);
		else if(k>t[x].val) del(rc(x),k);
		update(x);
		if(canrbu(x)) rbu(x);
	}
	int up_great(int x,int k){
		if(!x) return 0;
		if(k==t[x].val&&t[x].cnt) return t[lc(x)].fc;
		else if(k<t[x].val) return up_great(lc(x),k);
		else return up_great(rc(x),k)+t[lc(x)].fc+t[x].cnt;
	}
	int up_bound(int x,int k){
		if(!x) return 1;
		if(k==t[x].val&&t[x].cnt) return t[lc(x)].fc+t[x].cnt+1;
		else if(k<t[x].val) return up_bound(lc(x),k);
		else return up_bound(rc(x),k)+t[lc(x)].fc+t[x].cnt;
	}
	int kth(int x,int k){
		if(!x) return 0;
		if(t[lc(x)].fc<k&&k<=t[lc(x)].fc+t[x].cnt) return t[x].val;
		else if(t[lc(x)].fc+t[x].cnt<k) return kth(rc(x),k-t[lc(x)].fc-t[x].cnt);
		else return kth(lc(x),k);
	}
	inline int rk(int x,int k){
		return up_great(x,k)+1;
	}
	inline int pre(int x,int k){
		return kth(x,up_great(x,k));
	}
	inline int nxt(int x,int k){
		return kth(x,up_bound(x,k));
	}
};