Splay Tree

区间翻转

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#define fa(x) tree[x].fa
#define son(x, y) tree[x].son[y]
#define s(x) tree[x].size
#define rev(x) tree[x].rev
using namespace std;
const int MAXN = 1e5 + 10;

struct BinarySearchTree {
    int fa, son[2], size;
    bool rev;
} tree[MAXN];
int treeRoot, n, m;

inline void pushup(int x) {
    s(x) = s(son(x, 0)) + s(son(x, 1)) + 1;
}

inline void pushdown(int x) {
    if (rev(x)) {
        swap(son(x, 0), son(x, 1));
        rev(son(x, 0)) ^= 1;
        rev(son(x, 1)) ^= 1;
        rev(x) = 0;
    }
}

void rotate(int x, int& root) {
    // rotate x to upper layer (with root declared)
    // single-rotate
    int f = fa(x), g = fa(f);
    int relation = (x == son(f, 0)) ? 0 : 1;
    if (f == root) {
        // reached root
        root = x;
    }
    else {
        // connect x to g
        if (son(g, 0) == f) son(g, 0) = x;
        else                son(g, 1) = x;
    }
    // change remaining connections
    fa(x) = g;

    // f as son of x
    son(f, relation) = son(x, relation ^ 1);
    fa(son(f, relation)) = f;
    son(x, relation ^ 1) = f;
    fa(f) = x;

    // remember to pushup after rotation
    pushup(f);
   pushup(x);

    return;
}

void splay(int x, int& root) {
    // multiple rotate & move x to root
    // double-rotate at one time
    while (x != root) {
        int f = fa(x), g = fa(f);
        if (f != root) {
            // can do double rorate
            // then perform the first rotate here
            if ((son(f, 0) == x) ^ (son(g, 0) == f)) {
                // not in a line
                rotate(x, root);
            }
            else {
                // in a line
                rotate(f, root);
            }
        }
        // perform the second rotate
        rotate(x, root);
    }
    return;
}

void insert(int l, int r, int f) {
    if (l > r)
        return;
    int mid = (l + r) >> 1;
    // current node
    if (mid < f) son(f, 0) = mid;
    else         son(f, 1) = mid;
    // initialize current node
    fa(mid) = f, s(mid) = 1, rev(mid) = false;
    if (l == r)
        return;
    insert(l, mid - 1, mid);
    insert(mid + 1, r, mid);
    pushup(mid);
}

int query(int x, int k) { // find the node ranking kth
    pushdown(x);
    int size = s(son(x, 0));
    // size of (lson of x) + 1 represents the position of x
    if (size + 1 == k) {
        return x;
    }
    if (k <= size)
        return query(son(x, 0), k);
    else
        return query(son(x, 1), k - size - 1);
}

void reverse(int l, int r) {
    int x = query(treeRoot, l), y = query(treeRoot, r + 2); // node r + 2
    splay(x, treeRoot);
    splay(y, son(x, 1));
    // the lson of y is the interval to be reversed
    // note that at least, (x, y) must exists
    // so we must have 2 virtual nodes (endpoints) to maintain the whole interval
    rev(son(y, 0)) ^= 1;
    return;
}

int main() {
    scanf("%d%d", &n, &m);
    treeRoot = (n + 2 + 1) >> 1;
    insert(1, n + 2, treeRoot);
    while (m--) {
        int l, r;
        scanf("%d%d", &l, &r);
        reverse(l, r);
    }
    for (int i = 2; i <= n + 1; i++) // consider the virtual nodes
        printf("%d ", query(treeRoot, i) - 1); // as above
    return 0;
}