mx刚学指针，带父指针splay求调

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#define rep(i, a, b) for (int i = (a); i <= (b); i ++ )
#define rop(i, a, b) for (int i = (a); i < (b); i ++ )
#define dep(i, a, b) for (int i = (a); i >= (b); i -- )
#define dop(i, a, b) for (int i = (a); i > (b); i -- )

using namespace std;

using LL = long long;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;

int n, m;
struct node {
    node *s[2], *p;
    int v, size, rev;
    node() { s[0] = s[1] = p = NULL, size = 1, rev = v = 0; }
    void pushup() { size = (s[0] -> size + s[1] -> size + 1); }
    void pushrev() { swap(s[0], s[1]); rev ^= 1; }
    void pushdown() {
        if (rev) {
            s[0] -> pushrev(), s[1] -> pushrev();
            rev = 0;
        }
    }
}*root;

void rotate(node* x) {
    node* y = x -> p, *z = y -> p;
    int k = y -> s[1] == x;
    x -> p = z, z -> s[z -> s[1] == y] = x;
    y -> s[k] = x -> s[k ^ 1], x -> s[k ^ 1] -> p = y;
    x -> s[k ^ 1] = y, y -> p = x;
    y -> pushup(), x -> pushup();
}
void splay(node* x, node* k) {
    while (x -> p != k) {
        node *y = x -> p, *z = y -> p;
        if (z != k) {
            if ((z -> s[1] == y) ^ (y -> s[1] == x)) rotate(y);
            else rotate(x);
        }
        rotate(x);
    }
    if (k == NULL) root = x;
}
node *get_k(int k) {
    node *u = root;
    while (true) {
        u -> pushdown();
        if (u -> s[0] -> size >= k) u = u -> s[0];
        else if (u -> s[0] -> size + 1 == k) return u;
        else k -= u -> s[0] -> size + 1, u = u -> s[1];
    }
}
void insert(int v) {
    node *u = root, *p = NULL;
    while (u != NULL) {
        p = u, u = u -> s[v > u -> v];
    }
    u = new node(); u -> v = v;
    if (p != NULL) p -> s[v > p -> v] = u;
    u -> p = p; splay(u, NULL);
}

int main() {
    root = new node();
    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);
        node *x = get_k(l), *y = get_k(r + 2);
        splay(x, NULL); splay(y, x);
        y -> s[0] -> pushrev();
    }

    return 0;
}