splay

splay 是一种能支持区间操作的平衡树。

建树：

struct splay_tree{
	int f,c[2],cnt,size,val,la;//父亲、儿子、节点数量、子树大小、节点权值、懒标记
}t[N];

pushup 和 pushdown 操作：

void pushup(int p)
{
	t[p].size=t[t[p].c[0]].size+t[t[p].c[1]].size+t[p].cnt;
}
void pushdown(int p)
{
	swap(t[p].c[0],t[p].c[1]);
	t[p].la=0;
	t[t[p].c[0]].la^=1,t[t[p].c[1]].la^=1;//异或，因为翻转两次等于没翻
}

旋转操作：

图片

void rotate(int x)//将x与它的父亲旋转
{
	int y=t[x].f;// x的父亲
	int z=t[y].f;// x的祖宗
	int d=t[y].c[1]==x; //x为y的那个儿子
	t[z].c[t[z].c[1]==y]=x;//将 x接的y的位置上
	t[x].f=z;//更新x的父亲
	t[y].c[d]=t[x].c[d^1];//接下来和treap差不多，不过还要维护父亲节点
	t[t[x].c[d^1]].f=y;
	t[x].c[d^1]=y;
	t[y].f=x;
	pushup(y);//先y后x
	pushup(x);
}

splay 操作：

旋转的时候有两种情况：

图片1 图片2

第一种需先旋转y，第二种需先旋转x

然后都需旋转x，才能完成操作。

void splay(int x,int k)//将x旋转到k节点以（若k=0，即旋至根节点）
{
	while(t[x].f!=k){//转到k节点以下
		int y=t[x].f;
		int z=t[y].f;
		if(z!=k){//不能转到k节点
			if(!((t[z].c[1]==y)^(t[y].c[1]==x)))rotate(y);//分类讨论两种情况
			else rotate(x);
		}
		rotate(x);
	}
	if(k==0)root=x;//更新root
}

之后玄学的就来了。

我们每次插入一个值，都要把该值对应的节点splay到根节点。

这样就能保证复杂度为 $\log n $ ，证明就不是人能看懂的东西。总之splay操作有效避免了毒瘤的迫害（一条链）。

插入值 \(x\)

void insert(int x)
{
	int u=root,f=0; //从根节点向下找，同时记录父亲
	while(u&&t[u].val!=x){
		if(t[u].la)pushdown(u);//pushdown
		f=u;
		u=t[u].c[t[u].val<x];
	}
	if(u)t[u].cnt++;
	else{
		u=++idx;
		if(f)t[f].c[t[f].val<x]=u;//不能漏
		t[u].f=f;//不能漏
		t[u].val=x;
		t[u].size=t[u].cnt=1;
	}
	splay(u,0);//旋至根节点
}

找到值为 \(k\) 的节点。

int get_u(int k)
{
	int u=root;
	if(t[u].size<k)return 0;
	while(1){
		if(t[u].la)pushdown(u);//pushdown
		int y=t[u].c[0];
		if(t[y].size+1<k){
			k=k-t[y].size-1;//到右子树，k要减去相应的值
			u=t[u].c[1];
		}
		else{
			if(t[y].size+1>k)u=y;
			else return u;
		}
	}
}

区间操作：

处理节点 \(l\) 到 \(r\) 之间

spaly(l,0);
spaly(r+2,l);//有哨兵
solve(tr[r+1].ch[0])