给定一个序列，以及若干次反转区间的操作，要求输出经过若干次反转操作之后的序列。

题解

用 Splay 维护序列即可。

对于一棵平衡树，满足旋转后其中序遍历始终不变的性质，所以我们按照序列来确定初始的 Splay ，这样做的话， Splay 的每个节点代表的是序列上的某个位置。

而后，对于每次反转，其实就是反转某一棵中序遍历为 [l,r] [l, r] 的子树，这里我们将 l−1 l - 1 位置上的节点旋转到根，将 r+1 r + 1 位置上的节点旋转到根的右子树，由于这棵 Splay 的中序遍历就是原来的序列，那么 r+1 r + 1 位置上的节点的左子树的中序遍历一定是我们要的 [l,r] [l, r] 这段区间，将这个节点打上反转标记即可。

注意，访问某个节点的儿子的时候一定要记得下放标记。

此外，如果要在函数内修改参数的值，不要忘记引用。。

代码

#include <cassert>
#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
#ifdef DBG
    const int MAXN = 10;
#else
    const int MAXN = 100000;
#endif
int a[MAXN + 1];
struct Splay {
    struct Node {
        Node *c[2], *fa, **root;
        int size, x;
        bool isBound, rev;
        Node(Node *fa, Node **root, int x, bool isBound = false) :
            fa(fa), root(root), size(1), x(x), isBound(isBound), rev(false) {
                c[0] = c[1] = NULL;
        }
        Node *pushDown() {
            if (rev) {
                std::swap(c[0], c[1]);
                if (c[0]) c[0]->rev ^= 1;
                if (c[1]) c[1]->rev ^= 1;
                rev = false;
            }
            return this;
        }
        void maintain() {
            size = (c[0] ? c[0]->size : 0) + (c[1] ? c[1]->size : 0) + 1;
        }
        int relation() {
            return this == fa->c[1];
        }
        void rotate() {
            pushDown();
            Node *old = fa;
            int x = relation();
            if (old->fa) old->fa->c[fa->relation()] = this;
            fa = old->fa;
            old->c[x] = c[x ^ 1];
            if (c[x ^ 1]) c[x ^ 1]->fa = old;
            c[x ^ 1] = old;
            old->fa = this;
            old->maintain(), maintain();
            if (!fa) *root = this;
        }
        void splay(Node *target = NULL) {
            while (fa != target) {
                if (fa->fa) fa->fa->pushDown();
                fa->pushDown();
                if (fa->fa == target) rotate();
                else if (relation() == fa->relation()) fa->rotate(), rotate();
                else rotate(), rotate();
            }
        }
        int lSize() {
            return c[0] ? c[0]->size : 0;
        }
    } *root;
    Splay() : root(NULL) {}
    void build(int *a, int n) {
        root = build(a, 1, n, NULL);
        Node **v = &root, *fa = NULL;
        while (*v) {
            fa = *v;
            fa->size++;
            v = &(*v)->c[0];
        }
        *v = new Node(fa, &root, 0, true);
        v = &root, fa = NULL;
        while (*v) {
            fa = *v;
            fa->size++;
            v = &(*v)->c[1];
        }
        *v = new Node(fa, &root, 0, true);
    }
    Node *build(int *a, int l, int r, Node *fa) {
        if (l > r) return NULL;
        int mid = (l + r) >> 1;
        Node *v = new Node(fa, &root, a[mid - 1]);
        if (l != r) {
            v->c[0] = build(a, l, mid - 1, v);
            v->c[1] = build(a, mid + 1, r, v);
            v->maintain();
        }
        return v;
    }
    Node *select(int k) {
        k++;
        Node *v = root;
        while (k != v->pushDown()->lSize() + 1) {
            if (k < v->lSize() + 1) v = v->c[0];
            else k -= v->lSize() + 1, v = v->c[1];
        }
#ifdef DBG
        printf("Result before splay is %d\n", v->x);
#endif
        v->splay();
#ifdef DBG
        assert(root == v);
        printf("Result is %d\n", v->x);
        printf("------------------------------------------\n");
#endif
        return root;
    }
    Node *select(int l, int r) {
        Node *epl = select(l - 1), *epr = select(r + 1);
        epl->splay();
        epr->splay(epl);
        return epr->c[0];
    }
    void reverse(int l, int r) {
        Node *range = select(l, r);
        range->rev ^= 1;
    }
    void getAns(int *a) {
        dfs(a, root);
    }
    void dfs(int *&a, Node *v) {
        if (v) {
            v->pushDown();
            dfs(a, v->c[0]);
            if (!v->isBound) *a++ = v->x;
            dfs(a, v->c[1]);
        }
    }
#ifdef DBG
    void print(Node *v) {
        if (v) {
            v->pushDown();
            print(v->c[0]);
            printf("Size : %d, value : %d\n", v->size, v->x);
            print(v->c[1]);
        }
    }
#endif
} splay;
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) a[i] = i + 1;
    splay.build(a, n);
#ifdef DBG
    splay.print(splay.root);
    printf("--------------------------------------\n");
#endif
    while (m--) {
        int l, r;
        scanf("%d %d", &l, &r);
        splay.reverse(l, r);
#ifdef DBG
        splay.print(splay.root);
        printf("---------------------------------------------\n");
#endif
    }
    splay.getAns(a);
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    return 0;
}