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])