P3391 【模板】文艺平衡树
1. splay 函数将左旋右旋合并在一起。
2. 每插入一个数字就将它旋转到根节点位置。
3. 维护 flag 表示是否需要翻转，需要翻转就将左右子树调换一下并将标记下传。

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
struct node {
    int s[2], p, v;
    int size, flag;
    void init(int _v, int _p) {
        v = _v, p = _p;
        size = 1;
    }
} t[N];
int n, m, root, tot;

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

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

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

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

void insert(int v) {
    int u = root, p = 0;
    while(u) p = u, u = t[u].s[v > t[u].v];
    u = ++tot;
    if(p) t[p].s[v > t[p].v] = u;
    t[u].init(v, p);
    splay(u, 0);
}

int get_k(int k) {
    int u = root;
    while(1) {
        pushdown(u);
        if(t[t[u].s[0]].size >= k) u = t[u].s[0];
        else if(t[t[u].s[0]].size + 1 == k) return u;
        else k -= t[t[u].s[0]].size + 1, u = t[u].s[1];
    }
}

void output(int u) {
    pushdown(u);
    if(t[u].s[0]) output(t[u].s[0]);
    if(t[u].v >= 1 && t[u].v <= n) cout << t[u].v << " ";
    if(t[u].s[1]) output(t[u].s[1]);
}

int main() {
    cin >> n >> m;
    for(int i = 0; i <= n + 1; i++) insert(i);
    while(m--) {
        int l, r;
        cin >> l >> r;
        l = get_k(l), r = get_k(r + 2);
        splay(l, 0), splay(r, l);
        t[t[r].s[0]].flag ^= 1;
    }
    output(root);
    return 0;
}