翻转区间，用splay来做

splay如何保证树高不超过log n：
每次插入和查询都把那个节点旋转到根

splay(x,k):将点x旋转至k下面
splay(x,0):就是旋转到根

上图就是splay的过程

插入：
1.将一个序列插入y的后面:
找到y的后继z
splay(y,0)
splay(z,y)
易知z的左子树是空
把那个序列放在z的左子树就行了

删除:
1.删除从l到r的一段
找到l的前驱l-1,r的后继r+1
splay(l-1,0)
splay(r+1,l-1)
易知r+1的左子树就是序列l到r
将这一段设为空就好

其他操作跟普通平衡树一样

splay如何维护信息:
1.找第k个数:维护size
2.翻转区间:懒标记rev
3.pushup:root.size=left.size+right.size
4.pushdown:swap(l,r),标记下传

左旋右旋合并程序

void rotate(int x)
{
    int y=tr[x].p,z=tr[y].p;//y是x父节点，z是y父节点
    int k=tr[y].s[1]==x;//k代表y是x的左儿子还是右儿子
    tr[z].s[tr[z].s[1]==y]=x,tr[x].p=z;//z对应的儿子就是x,x的父节点是z
    tr[y].s[k]=tr[x].s[k^1],tr[tr[x].s[k^1]].p=y;//y的左儿子=x的右儿子,x的右儿子的父节点=y
    tr[x].s[k^1]=y,tr[y].p=x;//x的右儿子=y,y的父节点=x
    pushup(y),pushup(x);
}

splay的核心函数

void splay(int x,int k)
{
    while(tr[x].p!=k)//当x的父节点不等于k的时候
    {
        int y=tr[x].p,z=tr[y].p;//y是x的父节点,z是y的父节点
        if(z!=k) 
            if((tr[y].s[1]==x)^(tr[z].s[1]==y)) rotate(x);//折线关系
            else rotate(y);//直线关系
        rotate(x);
    }
    if(!k) root=x;
}