Treap

inline void update(int t)
{
	if (!t) return; 
	s[t]=s[l(t)]+s[r(t)]+1;
	sum[t]=sum[l(t)]+sum[r(t)]+k[t];
}

void RT(int &t){int x=l(t); l(t)=r(x); r(x)=t; update(t); update(x); t=x;}

void LT(int &t){int x=r(t); r(t)=l(x); l(x)=t; update(t); update(x); t=x;}

void Insert(int &t, int x)
{
	if (!t) t=++cn, l(t)=r(t)=0, s[t]=1, k[t]=sum[t]=x, Rn[t]=rand();
	else if (x<k[t])
	{
		Insert(l(t),x); update(t);
		if (Rn[l(t)]>Rn[t]) RT(t);
	}
	else
	{
		Insert(r(t),x); update(t);
		if (Rn[r(t)]>Rn[t]) LT(t);
	}
}

void Delete(int &t, int x)
{
	if (x==k[t])
	{
		if (!l(t)) t=r(t);
		else if (!r(t)) t=l(t);
		else if (Rn[l(t)]>Rn[r(t)]) 
			RT(t), Delete(r(t), x);
		else 
			LT(t), Delete(l(t), x);
	} else Delete(x<k[t]?l(t):r(t), x);
	update(t);
}

Splay-单旋

void Splay(int x, int &k)
{
	int y, z;
	if (rev[x]) putdown(x); 
	while (x!=k) 
	{
		if (rev[h[x]]) putdown(h[x]), putdown(x);
		y=h[x], z=h[y]; if (y==k) k=x; else r(z)==y?r(z)=x:l(z)=x;
		if (l(h[x])==x)
			h[r(x)]=y, h[y]=x, h[x]=z, l(y)=r(x), r(x)=y;  //RT
		else
			h[l(x)]=y, h[y]=x, h[x]=z, r(y)=l(x), l(x)=y;  //LT
		update(y);
	}
	update(x);
}

int Find(int s)
{
	int t=rt; while (true)
	{
		if (rev[t]) putdown(t);
		if (s<sz[l(t)]) t=l(t);
		else if (s==sz[l(t)]) return t;
		else if (s>sz[l(t)]) s-=sz[l(t)]+1, t=r(t);
	}
}

int Build(int l, int r)
{
	if (l>r) return 0; int mid=(l+r)>>1;
	l(mid)=Build(l,mid-1); r(mid)=Build(mid+1,r); h[l(mid)]=h[r(mid)]=mid;
	update(mid); return mid;
}

LCT

inline void Rev(int x){rev[x]^=1, swap(l(x),r(x));}
inline void putdown(int x){if (l(x)) Rev(l(x)); if (r(x)) Rev(r(x)); rev[x]=0;}

inline void Rot(int x, int y)
{
	if (rev[y]) putdown(y); if (rev[x]) putdown(x);
	if (h[y]>0) l(h[y])==y?l(h[y])=x:r(h[y])=x; h[x]=h[y], h[y]=x;
	if (l(y)==x) 
		l(y)=r(x), r(x)=y, h[l(y)]=y;
	else
		r(y)=l(x), l(x)=y, h[r(y)]=y;
}
inline void Splay(int x)
{
	while (h[x]>0)
	{
		int y=h[x], z=h[y];
		if (z<=0 || (l(y)==x)^(l(z)==y))
			Rot(x,y);
		else
			Rot(y,z);
	}
}

inline void Cut(int x){if (rev[x]) putdown(x); if (r(x)) h[r(x)]=-x, r(x)=0;}
inline void Link(int x, int y){if (rev[x]) putdown(x); if (y) r(x)=y, h[y]=x;}
inline void Access(int x)
{
	for(int a=x, b=0; a; b=a, a=-h[a]) Splay(a), Cut(a), Link(a,b);
	Splay(x); Rev(x);
}

inline int FindRT(int x){while (h[x]!=0) x=abs(h[x]); return x;}
inline int Findrt(int x){while (h[x]>0) x=h[x]; return x;}

斜堆

有关斜堆的介绍（维基中文）

int st[maxn], top;
inline int Join(int x, int y)
{
	if (!y) return x; if (!x) return y;
	top=0; while (x || y)
	{
		if (k[x]<k[y]) swap(x,y);
		st[++top]=x, sz[x]-=sz[r(x)], sum[x]-=sum[r(x)], x=r(x);
	}
	while (top>1)
		r(st[top-1])=l(st[top-1]), l(st[top-1])=st[top], sz[st[top-1]]+=sz[st[top]], sum[st[top-1]]+=sum[st[top]], top--;
	return st[1];
}
inline void Push(int &t){t=Join(l(t),r(t));}

替罪羊树(Scapegoat tree)

原理：

每次操作以后检查操作路径，找到最高的满足 $max(size(son_L),size(son_R))>alpha*size(this)$ 的结点，重建整个子树

#define alpha 0.75

int tmp; 

// 在遍历完子树之后……
if (max(sz[l(t)],sz[r(t)])<sz[t]*alpha) // 平衡
{
	if (tmp) reBuild(tmp), tmp=0;
}
else tmp=t;  // 不平衡