$简介$

Splay 树(伸展树)，是一种平衡二叉查找树，它通过 Splay操作 不断将某个节点旋转到根节点，使得整棵树仍然满足二叉查找树的性质，能够在均摊 时间内完成插入，查找和删除操作，并且保持平衡而不至于退化为链。

$基本操作$

1. 更新操作：用子节点的信息更新父节点
2. 下传操作：将父节点的信息下传到子节点

$Code$

void pushup(int u)
{
    tr[u].size = tr[tr[u].s[0]].size + tr[tr[u].s[1]].size + 1;
}

void pushdown(int u)
{
    if (tr[u].flag)//此处为旋转操作,可改为其他操作
    {
        swap(tr[u].s[0], tr[u].s[1]);
        tr[tr[u].s[0]].flag ^= 1;
        tr[tr[u].s[1]].flag ^= 1;
        tr[u].flag = 0;
    }
}

$旋转操作$

在保持整棵二叉树性质的情况下，使二叉树尽量平衡

Code

void rotate(int x) //将x左旋或右旋
{
    int y = tr[x].p, z = tr[y].p;//y表示x的父节点,z表示x的祖父节点
    int k = tr[y].s[1] == x;//k为1表示x为左儿子，k为0表示x为右儿子
    tr[z].s[tr[z].s[1] == y] = x, tr[x].p = z;
    tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;
    tr[x].s[k ^ 1] = y, tr[y].p = x;
    pushup(y), pushup(x);//更换信息
}

$Splay 操作$

Splay 操作规定：每访问一个节点 后都要强制将其旋转到目标节点。

y为x的父节点，z为y的父节点

$规则$：

1. 若x和y都为父节点的左儿子或右儿子,那么先旋转y，再旋转x
   
2. 否则旋转两次x
   

Code

void splay(int x, int k) 
{
    while (tr[x].p != k) 
    {
        int y = tr[x].p, z = tr[y].p;
        if (z != k)
            (tr[y].s[0] == x) ^ (tr[z].s[0] == y) ? rotate(x) : rotate(y);
        rotate(x);
    }
    if (!k)root = x;
}

$插入操作$

由于Splay是一棵二叉搜索树,所以可以先将x按SBT的插入方式插入Splay树,再将x旋转至根节点保持平衡

Code

void insert(int v) 
{
    int u = root, p = 0;
    while (u)p = u, u = tr[u].s[v > tr[u].v];//寻找
    u = ++ idx;//建立节点
    if (p)tr[p].s[v > tr[p].v] = u;
    tr[u].p = p, tr[u].v = v, tr[u].size = 1;
    splay(u, 0);//旋转
}

$查询排名$

与SBT一样,一层层深入,找到此点

Code

int get_rank(int k) {
    int u = root;
    while (true) {
        pushdown(u);
        if (k <= tr[tr[u].s[0]].size)u = tr[u].s[0];
        else if (k == tr[tr[u].s[0]].size + 1)return u;
        else k -= tr[tr[u].s[0]].size + 1, u = tr[u].s[1];
    }
    return -1;
}

$Splay模板$

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
int n, m;
int root, idx;

struct Node {
    int s[2], v, p;
    int flag, size;
}tr[N];

void pushup(int u)
{
    tr[u].size = tr[tr[u].s[0]].size + tr[tr[u].s[1]].size + 1;
}

void pushdown(int u)
{
    if (tr[u].flag)
    {
        swap(tr[u].s[0], tr[u].s[1]);
        tr[tr[u].s[0]].flag ^= 1;
        tr[tr[u].s[1]].flag ^= 1;
        tr[u].flag = 0;
    }
}

void rotate(int x) {
    int y = tr[x].p, z = tr[y].p;
    int k = tr[y].s[1] == x;
    tr[z].s[tr[z].s[1] == y] = x, tr[x].p = z;
    tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;
    tr[x].s[k ^ 1] = y, tr[y].p = x;
    pushup(y), pushup(x);
}

void splay(int x, int k) {
    while (tr[x].p != k) {
        int y = tr[x].p, z = tr[y].p;
        if (z != k)
            (tr[y].s[0] == x) ^ (tr[z].s[0] == y) ? rotate(x) : rotate(y);
        rotate(x);
    }
    if (!k)root = x;
}

void insert(int v) {
    int u = root, p = 0;
    while (u)p = u, u = tr[u].s[v > tr[u].v];
    u = ++ idx;
    if (p)tr[p].s[v > tr[p].v] = u;
    tr[u].p = p, tr[u].v = v, tr[u].size = 1;
    splay(u, 0);
}

int get_rank(int k) {
    int u = root;
    while (true) {
        pushdown(u);
        if (k <= tr[tr[u].s[0]].size)u = tr[u].s[0];
        else if (k == tr[tr[u].s[0]].size + 1)return u;
        else k -= tr[tr[u].s[0]].size + 1, u = tr[u].s[1];
    }
    return -1;
}

void output(int u) {
    pushdown(u);
    if (tr[u].s[0])output(tr[u].s[0]);
    if (1 <= tr[u].v && tr[u].v <= n)printf("%d ", tr[u].v);
    if (tr[u].s[1])output(tr[u].s[1]);
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i <= n + 1; i ++ )insert(i);
    while (m -- ) {
        int l, r;
        scanf("%d%d", &l, &r);
        l = get_rank(l), r = get_rank(r + 2);
        splay(l, 0), splay(r, l);
        tr[tr[r].s[0]].flag ^= 1;//懒标记
    }
    output(root);//输出中序遍历
    return 0;
}