Splay

解题思路

本题是 Splay 的一个模板题，肯定是要用 Splay 来维护的。

每次要将 $[l, r]$ 这个序列进行翻转，因此每次我们需要快速知道第 $l$ 个数和第 $r$ 个数在什么位置，因此我们可以维护一个 $cnt$ 表示以每个节点为根节点的子树上的节点个数。由于我们还需要翻转序列，其实是一个区间修改的操作，因此我们还需要一个懒标记 $flag$ 表示以每个节点为根节点的子树通过中序遍历得到的序列是否需要翻转。

每个节点的 $cnt$ 信息都可以通过两个子节点的 $cnt$ 来得到，而懒标记则在递归的过程中直接向下传递即可，因此本题需要的信息我们都可以轻松维护，不需要进行额外的处理，只是一个简单的 Splay 的应用。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010;

int n, m;

struct Node
{
    int s[2], p, v; //两个子节点的位置、父节点的位置、编号
    int cnt, flag; //当前子树中节点个数、当前子树所对应的序列是否需要翻转（懒标记）

    void init(int _v, int _p) //初始化函数
    {
        v = _v, p = _p;
        cnt = 1;
    }
}tr[N]; //Splay
int root, idx; //根节点、指针

void pushup(int u) //通过子节点的信息得到当前节点的信息
{
    tr[u].cnt = tr[tr[u].s[0]].cnt + tr[tr[u].s[1]].cnt + 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; //y 是 x 的父节点，z 是 y 的父节点
    int k = tr[y].s[1] == x; //k = 0 表示 x 是 y 的左子节点，k = 1 表示 x 是 y 的右子节点

    //k = 0 对应右旋，k = 1 对应左旋
    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) //将 x 转到 k 的下面
{
    while(tr[x].p != k) //只要 x 还不是 k 的子节点，就将 x 往上转
    {
        int y = tr[x].p, z = tr[y].p;
        if(z != k) //z 不等于 k，说明 x 还要转至少两次，否则只需要转一次就行
        {
            if((tr[y].s[1] == x) ^ (tr[z].s[1] == y)) rotate(x); //如果三个点呈折线，那么第一次要把 x 往上转
            else rotate(y); //如果三个点呈直线，那么第一次要把 y 往上转
        }
        rotate(x); //第二次固定把 x 往上转（如果只需要转一次，也是把 x 往上转）
    }
    if(!k) root = x; //如果 k = 0，说明要将 x 转到根节点，这时需要实时更新根节点是谁
}

void insert(int v) //将 v 插入 Splay
{
    int u = root, p = 0; //记录 v 应该插到哪个点后面，p 是 u 的父节点
    while(u) p = u, u = tr[u].s[v > tr[u].v]; //往下找到 v 应该插入的位置
    u = ++idx; //给 u 赋上一个新的下标
    if(p) tr[p].s[v > tr[p].v] = u; //更新 p 的信息
    tr[u].init(v, p); //初始化 u 的信息
    splay(u, 0); //将操作的节点转到根节点
}

int get_k(int k) //找到第 k 个数的下标（注意，第 k 个数指中序遍历的第 k 个数）
{
    int u = root; //记录第 k 个数的下标，从根节点往下找
    while(true)
    {
        pushdown(u); //递归之前先将懒标记下传
        if(tr[tr[u].s[0]].cnt >= k) u = tr[u].s[0]; //如果左子树上节点个数 >= k，说明第 k 个数在左子树上
        else if(tr[tr[u].s[0]].cnt + 1 == k) return u; //如果左子树上节点个数 + 1 == k，说明当前节点就是第 k 个数
        else k -= tr[tr[u].s[0]].cnt + 1, u = tr[u].s[1]; //否则说明第 k 个数在右子树上，去右子树中继续找，同时 k 需要减去除右子树以外的所有节点个数
    }
    return -1;
}

void print(int u) //输出整棵树的中序遍历
{
    pushdown(u); //递归之前先将懒标记下传

    if(tr[u].s[0]) print(tr[u].s[0]); //如果存在左子节点，递归左子节点
    if(tr[u].v >= 1 && tr[u].v <= n) printf("%d ", tr[u].v); //如果当前节点不是哨兵，输出当前节点的值
    if(tr[u].s[1]) print(tr[u].s[1]); //如果存在右子节点，递归右子节点
}

int main()
{
    scanf("%d%d", &n, &m);

    //在操作过程中一般会找前驱和后继，这时可能会存在边界问题，因此加入两个哨兵 0 和 n + 1 来防止边界问题
    for(int i = 0; i <= n + 1; i++) insert(i); //将所有节点插入 Spaly

    while(m--)
    {
        int l, r;
        scanf("%d%d", &l , &r);
        l++, r++; //由于加入了哨兵，所有编号都要加上 1
        l = get_k(l - 1), r = get_k(r + 1); //要想对 [l, r] 进行操作，需要找到 l 的前驱 l - 1 和 r 的后继 r + 1
        splay(l, 0), splay(r, l); //将 l - 1 转到根，将 r + 1 转到 l - 1 的下面，这样 [l, r] 整个序列就在 r + 1 的左子树上
        tr[tr[r].s[0]].flag ^= 1; //将 [l, r] 整个序列翻转一下，即对 r + 1 的左子树进行标记
    }
    print(root); //输出序列，即整棵树的中序遍历

    return 0;
}