题解

模板题，代码中详细

代码

// 题解：https://www.acwing.com/solution/content/34350/
#include <iostream>

using namespace std;
const int N = 1e5 + 4;
int n, m;
struct Node {
    int s[2], p, v;
    int size, flag;
    void init(int _v, int _p) {
        p = _p;
        v = _v;
        size = 1;
    }
} tr[N];
int root, idx;
void pushup(int x) {
    // 利用子节点更新父节点
    tr[x].size = tr[tr[x].s[0]].size + tr[tr[x].s[1]].size + 1;
}
void rotate(int x) {
    // 左旋或右旋操作, 取出当前节点x的父节点x、祖父节点z
    int y = tr[x].p, z = tr[y].p;
    // k=0表示x是y的左儿子；k=1表示x是y的右儿子
    int k = tr[y].s[1] == x;
    // z的儿子y换成孙子x，即x，y地位互换
    tr[z].s[tr[z].s[1] == y] = x, tr[x].p = z;
    // 用x[原来x在y反方向上]的儿子代替x在y中的位置
    // 举例：x是y的左儿子，那么替换后y的左儿子就是x右儿子
    tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;
    // 将y归为x儿子，原来的反方向，因为大小变了，方向自然要变
    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) {
            // 祖父不是根，需要进行两次旋转。这里判断是否三点共线
            // 共线的话是需要旋转父节点，不共线的话需要旋转自己节点
            if ((tr[y].s[1] == x) ^ (tr[z].s[1] == y)) {
                // 如果为真，说明一个是右儿子，一个是左儿子，先旋转自己
                rotate(x);
            } else {
                // 旋转父节点
                rotate(y);
            }
        }
        // 父是根，旋转自身一次就可以到根
        rotate(x);
    }
    // 如果当前节点是0，就是根
    if (!k) root = x;
}
void insert(int v) {
    // u是当前节点，p是父节点
    int u = root, p = 0;
    while (u) {
        p = u;
        u = tr[u].s[v > tr[u].v];
    }
    u = ++idx;
    // 如果此时是根节点0
    if (p) tr[p].s[v > tr[p].v] = u;
    tr[u].init(v, p);
    // 将u旋转到根节点
    splay(u, 0);
}
void pushdown(int x) {
    // 如果当前节点需要反转
    if (tr[x].flag) {
        // 先翻转自身的左右子树
        swap(tr[x].s[0], tr[x].s[1]);
        // 再去翻转左右儿子, 通过下传标记，只相当于下传一下，以后需要翻转才翻转
        tr[tr[x].s[0]].flag ^= 1, tr[tr[x].s[1]].flag ^= 1;
        // 清空当前标记
        tr[x].flag = 0;
    }
}
void output(int u) {
    // 先下传标记
    pushdown(u);
    // 中序遍历输出
    // 如果u有左儿子 先递归输出左儿子
    if (tr[u].s[0]) output(tr[u].s[0]);
    // 如果u不是哨兵输出当前点
    if (tr[u].v >= 1 && tr[u].v <= n) printf("%d ", tr[u].v);
    // 如果u有右儿子 递归输出右儿子
    if (tr[u].s[1]) output(tr[u].s[1]);
}
int get_k(int k) {
    int u = root;
    while (true) {
        //先下传懒标记
        pushdown(u);
        // 如果左子树个数>=k 则去左子树里看
        if (tr[tr[u].s[0]].size >= k) u = tr[u].s[0];
        // 如果左子树个数=k-1,则u就是中序遍历第k个点
        else if (tr[tr[u].s[0]].size + 1 == k)
            return u;
        else
            // 否则去右子树里看
            k -= tr[tr[u].s[0]].size + 1, u = tr[u].s[1];
    }
    return -1; //找不到返回-1,根本不可能执行
}

int main() {

    int l, r;
    scanf("%d%d", &n, &m);
    // 0和n + 1为哨兵
    for (int i = 0; i <= n + 1; i++)
        insert(i);

    while (m--) {
        scanf("%d%d", &l, &r);
        //因为哨兵要翻转的从[L,R]变为[L+1,R+1]
        //则要找L和R+2作为L+1的前继和R+1的后继
        l = get_k(l), r = get_k(r + 2);
        // l = 1, r = 2;
        // 左端点l转到根,右端点r转到左端点下面
        splay(l, 0), splay(r, l);
        // 只要将r的左子树[L+1,R+1]翻转
        tr[tr[r].s[0]].flag ^= 1;
    }
    output(root);
    return 0;
}