更好的阅读体验
splay是处理序列问题很常见的数据结构
这里给出指针版，数组版不同的代码
指针版需要注意的细节比较多，但是可以动态开点和释放空间，在速度上也更快
数组版，更适合处理区间问题
指针版，在分裂，合并上有优势，需要的时候可以做到动态释放空间

splay的基本操作

BZOJ1588

指针版

const int maxn = 1e6 + 8;
const int mod = 1000000;
const int inf = 0x3f3f3f3f;
int n;

// == tree structure ==
class Node {
public:
    static Node *root;
#define root Node::root
    Node* pa;
    Node* cld[2];

    int val, cnt;
    Node() {}

    Node(int v, Node* pa) : val(v), pa(pa) {
        cld[0] = cld[1] = NULL;
        cnt = 1;
    }

    int sgn() {
        return pa->cld[1] == this;
    }

    void setc(int d, Node* x) {
        cld[d] = x;
        if(x) x->pa = this;
    }

    void rot(int d) {
        Node *y = pa, *z = y->pa;
        if(z) z->setc(y->sgn(), this);
        if(y) y->setc(d, cld[d^1]);
        setc(d^1, y);
    }

    void rot() {
        rot(sgn());
    }

    Node* splay(const Node* to) {
        if(this == to) return this;

        while (pa != to) {
            if(pa == NULL) {
                root = this;
                break;
            }

            if(pa->pa == to) {
                rot();
                break;
            }
            else {
                int a = sgn(), b = pa->sgn();
                (a^b ? this : pa)->rot(a);
                rot(b);
            }
        }

        return this;
    }
} *root;

typedef Node* T;

void build() {
    root = new Node(-inf, NULL);
    root->cld[1] = new Node(inf, root);
}
// == tree structure finished ==

// == debug ==
void dbg(const T& rt) {
    T p = rt;
    if(p->cld[0]) dbg(p->cld[0]);

    printf("\n");
    debug(p->val);
    if(p->pa) debug(p->pa->val);

    if(p->cld[1]) dbg(p->cld[1]);
}
// == debug finsihed ==



// == void insert operation ==
void insert(const T& p, int x) {
    T u = p;
    T pa = NULL;

    while (u && u->val != x) {
        pa = u;
        u = u->cld[x > u->val];
    }

    if(u != NULL) u->cnt++;
    else {
        if(pa != NULL) {
            u = new Node(x, pa);
            pa->cld[x > pa->val] = u;
        }
        else {
            u = new Node(x, NULL);
            root = u;
        }
    }

    u->splay(root);
}
// == insert finsihed ==

// == delete data ==
T find(int x) {
    T u = root;
    while (true) {
        if(x == u->val) return u;
        if(u->cld[x > u->val] == NULL) return NULL;
        u = u->cld[x > u->val];
    }
}

void del(int x) {
    T u = find(x);
    if(u == NULL) return;

    u->splay(root);

    if(u->cnt > 1) {
        u->cnt--;
        return;
    }

    if(u->cld[0] == NULL) {
        int d = u->sgn();
        u->pa->setc(d, u->cld[1]);
        delete u;
        u = NULL;
    }
    else {
        int d = u->sgn();
        T pre = u->cld[0];
        while (pre->cld[1]) pre = pre->cld[1];

        pre->splay(u);
        pre->setc(1, u->cld[1]);
        u->pa->setc(d, pre);
        delete u;
        u = NULL;
    }
}

void rmvTree(T& p) {
    if(p->cld[0]) rmvTree(p->cld[0]);
    if(p->cld[1]) rmvTree(p->cld[1]);
    delete p;
    p = NULL;
}
// == delete finsihed ==

// == precursor and successor ==
int getNxt(const T& rt, int val) {
    int ans = inf;
    T p = rt;

    while (p) {
        if(val == p->val) {
            if(p->cnt >= 1) {
                ans = p->val;
                return ans;
            }
            if(p->cld[1]) {
                p = p->cld[1];
                while (p->cld[0]) p = p->cld[0];
                ans = p->val;
            }
            break;
        }
        if(p->val > val && p->val < ans) ans = p->val;
        p = val < p->val ? p->cld[0] : p->cld[1];
    }
    return ans;
}

int getPre(const T& rt, int val) {
    int ans = -inf;
    T p = rt;

    while (p) {
        if(val == p->val) {
            if(p->cnt >= 1) {
                ans = p->val;
                return ans;
            }
            if(p->cld[0]) {
                p = p->cld[0];
                while (p->cld[1]) p = p->cld[1];
                ans = p->val;
            }
            break;
        }
        if(p->val < val && p->val > ans) ans = p->val;
        p = val < p->val ? p->cld[0] : p->cld[1];
    }
    return ans;
}
// == precursor finished ==

int ans = 0;
void init() {
    ans = 0;
}

int main() {
    freopen("input.txt", "r", stdin);

    build();
    init();

    scanf("%d", &n);
    scanf("%d", &ans);
    n--;

    insert(root, ans);
    while (n--) {
        int x;
        scanf("%d", &x);
        int pre = getPre(root, x);
        int nxt = getNxt(root, x);
        ans += min(abs(pre - x), abs(nxt - x));

        insert(root, x);
    }
    printf("%d", ans);
    rmvTree(root);
}

数组版

const int maxn = 1e6 + 10;
const int mod = 1000000;
const int inf = 0x3f3f3f3f;
const int NIL = 0;
int n;

// == define tree ==
class Node {
public:
    int pa;
    int cld[2];
    int val, cnt;
} node[maxn];

inline int sgn(int x) {
    return node[node[x].pa].cld[1] == x;
}

int tot = 0;
int root;

int New(int val, int pa) {
    node[++tot].val = val;
    node[tot].pa = pa;
    node[tot].cnt = 1;
    return tot;
}

void build() {
    root = New(-inf, NIL);
    node[root].cld[1] = New(inf, root);
}

void dbg(int p) {
    if(node[p].cld[0]) dbg(node[p].cld[0]);

    printf("\n");
    debug(node[p].val);
    debug(node[node[p].pa].val);

    if(node[p].cld[1]) dbg(node[p].cld[1]);
}
// == tree finished ==

// == rotate ==
void setc(int q, int d, int p) {
    if(p) node[p].pa = q;
    if(q) node[q].cld[d] = p;
    if(q == NIL) root = p;
}

inline void rot(int x, int d) {
    int y = node[x].pa, z = node[y].pa;

    if(z) setc(z, sgn(y), x);
    if(y) setc(y, d, node[x].cld[d^1]);
    setc(x, d^1, y);
}

inline void rot(int x) {
    rot(x, sgn(x));
}
// == rotate finished ==

// == void splay ==
int splay(int p, const int to) {
    if(p == to) return p;

    while (node[p].pa != to) {
        if(node[p].pa == NIL) {
            root = p;
            break;
        }

        if(node[node[p].pa].pa == to) {
            rot(p);
            break;
        }
        else {
            int a = sgn(p), b = sgn(node[p].pa);
            rot((a^b ? p : node[p].pa), a);
            rot(p, b);
        }
    }
    return p;
}
// == splay finished ==

// == insert element ==
void insert(const int p, int x) {
    int u = p;
    int pa = NIL;

    while (u && node[u].val != x) {
        pa = u;
        u = node[u].cld[x > node[u].val];
    }

    if(u) node[u].cnt++;
    else {
        if(pa) {
            u = New(x, pa);
            node[pa].cld[x > node[pa].val] = u;
        }
        else {
            u = New(x, NIL);
            root = u;
        }
    }

    splay(u, root);
}
// == insert finished ==

// == delete element ==
int find(int x) {
    int u = root;
    while (true) {
        if(node[u].val == x) return u;
        if(node[u].cld[x > node[u].val] == 0) return NIL;
        u = node[u].cld[x > node[u].val];
    }
}

void _del(int x) {
    node[x].cld[0] = node[x].cld[1] = 0;
    node[x].pa = 0;
    node[x].val = node[x].cnt = 0;

    if(x == tot) tot--;
}

void del(int x) {
    int u = find(x);
    if(u == NIL) return;

    splay(u, root);

    if(node[u].cnt > 1) {
        node[u].cnt--;
        return;
    }

    if(node[u].cld[0] == 0) {
        int d = sgn(u);
        setc(node[u].pa, d, node[u].cld[1]);
        _del(u);
    }
    else {
        int d = sgn(u);
        int pre = node[u].cld[0];
        while (node[pre].cld[1]) pre = node[pre].cld[1];

        splay(pre, u);

        setc(pre, 1, node[u].cld[1]);
        setc(node[u].pa, d, pre);
        _del(u);
    }
}
// == delete finsihed ==

// == pre and next ==
int getPre(const int rt, int val) {
    int ans = -inf;
    int p = rt;

    while (p) {
        if(node[p].val == val) {
            if(node[p].cnt >= 1) {
                ans = node[p].val;
                return ans;
            }
            if(node[p].cld[0]) {
                p = node[p].cld[0];
                while (node[p].cld[1]) p = node[p].cld[1];
                ans = node[p].val;
            }
            break;
        }
        if(node[p].val < val && node[p].val > ans) ans = node[p].val;
        p = val < node[p].val ? node[p].cld[0] : node[p].cld[1];
    }
    return ans;
}

int getNxt(const int rt, int val) {
    int ans = inf;
    int p = rt;

    while (p) {
        if(node[p].val == val) {
            if(node[p].cnt >= 1) {
                ans = node[p].val;
                return ans;
            }
            if(node[p].cld[1]) {
                p = node[p].cld[1];
                while (node[p].cld[0]) p = node[p].cld[0];
                ans = node[p].val;
            }
            break;
        }
        if(node[p].val > val && node[p].val < ans) ans = node[p].val;
        p = val < node[p].val ? node[p].cld[0] : node[p].cld[1];
    }
    return ans;
}
// == pre and next finsihed ==

int main() {
    freopen("input.txt", "r", stdin);

    scanf("%d", &n);
    build();

    int ans;
    scanf("%d", &ans);
    insert(root, ans);
    n--;

    while (n--) {
        int x;
        scanf("%d", &x);

        int pre = getPre(root, x);
        int nxt = getNxt(root, x);

        ans += min(abs(pre - x), abs(nxt - x));

        insert(root, x);
    }

    printf("%d", ans);
}

splay的插入和删除

BZOJ1208

指针版

const int maxn = 1e6 + 8;
const int mod = 1000000;
const int inf = 0x3f3f3f3f;
int n;

// == tree structure ==
class Node {
public:
    static Node *root;
#define root Node::root
    Node* pa;
    Node* cld[2];

    int val, cnt;

    Node() {}

    Node(int v, Node* pa) : val(v), pa(pa) {
        cld[0] = cld[1] = NULL;
        cnt = 1;
    }

    int sgn() {
        return pa->cld[1] == this;
    }

    void setc(int d, Node *x) {
        cld[d] = x;
        if(x) x->pa = this;
    }

    void rot(int d) {
        Node *y = pa, *z = y->pa;
        if(z) z->setc(y->sgn(), this);
        if(y) y->setc(d, cld[d^1]);
        setc(d^1, y);
    }

    void rot() {
        rot(sgn());
    }

    Node *splay(const Node *to) {
        if(this == to) return this;

        while (pa != to) {
            if(pa == NULL) {
                root = this;
                break;
            }
            if(pa->pa == to) {
                rot();
                break;
            }
            else {
                int a = sgn(), b = pa->sgn();
                (a^b ? this : pa)->rot(a);
                rot(b);
            }
        }

        return this;
    }
} *root;

typedef Node* T;

void build() {
    root = new Node(-inf, NULL);
    root->cld[1] = new Node(inf, root);
}

// == tree structure finished ==

// == debug ==
void dbg(const T& rt) {
    T p = rt;
    if(p->cld[0]) dbg(p->cld[0]);
    printf("\n");
    debug(p->val);
    if(p->pa) debug(p->pa->val);
    if(p->cld[1]) dbg(p->cld[1]);
}
// == debug finished ==



// == insert operation ==
void insert(const T& p, int x) {
    T u = p;
    T pa = NULL;

    while (u && u->val != x) {
        pa = u;
        u = u->cld[x > u->val];
    }

    if(u != NULL) u->cnt++;
    else {
        if(pa != NULL) {
            u = new Node(x, pa);
            pa->cld[x > pa->val] = u;
        }
        else {
            u = new Node(x, NULL);
            root = u;
        }
    }
    u->splay(root);
}
// == insert finsihed ==

// == remove tree ==
T find(int x) {
    T u = root;
    while (true) {
        if(u->val == x) return u;
        if(u->cld[x > u->val] == NULL) return NULL;
        u = u->cld[x > u->val];
    }
}

void del(int x) {
    T u = find(x);
    if(u == NULL) return;

    u->splay(root);
    if(u != root) assert(u->pa == root);

    if(u->cnt > 1) {
        u->cnt--;
        return;
    }

    if(u->cld[0] == NULL) {
        int d = u->sgn();
        u->pa->setc(d, u->cld[1]);
        delete u;
        u = NULL;
    }
    else {
        int d = u->sgn();
        T pre = u->cld[0];
        while (pre->cld[1]) pre = pre->cld[1];

        pre->splay(u);
        assert(u->cld[0] == pre);

        pre->setc(1, u->cld[1]);
        u->pa->setc(d, pre);
        delete u;
        u = NULL;
    }
}

void rmvTree(T& p) {
    if(p->cld[0]) rmvTree(p->cld[0]);
    if(p->cld[1]) rmvTree(p->cld[1]);
    delete p;
    p = NULL;
}
// == remove finished ==

// == previous and successor ==
int getNxt(const T& rt, int val) {
    int ans = inf;
    T p = rt;

    while (p) {
        if(val == p->val) {
            if(p->cnt >= 1) {
                ans = p->val;
                return ans;
            }
            if(p->cld[1]) {
                p = p->cld[1];
                while (p->cld[0]) p = p->cld[0];
                ans = p->val;
            }
            break;
        }
        if(p->val > val && p->val < ans) ans = p->val;
        p = val < p->val ? p->cld[0] : p->cld[1];
    }
    return ans;
}

int getPre(const T& rt, int val) {
    int ans = -inf;
    T p = rt;

    while (p) {
        if(val == p->val) {
            if(p->cnt >= 1) {
                ans = p->val;
                return ans;
            }
            if(p->cld[0]) {
                p = p->cld[0];
                while (p->cld[1]) p = p->cld[1];
                ans = p->val;
            }
            break;
        }
        if(p->val < val && p->val > ans) ans = p->val;
        p = val < p->val ? p->cld[0] : p->cld[1];
    }
    return ans;
}
// == pre and successor finished ==



int petnum = 0, ans = 0;

void init() {
    petnum = 0;
    ans = 0;
}

int main() {
    freopen("input.txt", "r", stdin);

    init();
    scanf("%d", &n);

    build();

    while (n--) {
        int opt;
        scanf("%d", &opt);
        int x;
        scanf("%d", &x);

        if(petnum == 0) {
            insert(root, x);
            if(opt == 0) petnum++;
            else petnum--;
        }
        else if(petnum > 0) {
            // all pet
            if(opt == 0) {
                insert(root, x);
                petnum++;
            }
            else {
                int pre = getPre(root, x);
                int nxt = getNxt(root, x);

                if(abs(pre - x) <= abs(nxt - x)) {
                    del(pre);
                    ans = (ans + abs(pre - x)) % mod;
                    //debug(x);
                }
                else {
                    del(nxt);
                    ans = (ans + abs(nxt - x)) % mod;
                    //debug(x);
                }

                petnum--;
            }
        }
        else {
            // all people
            assert(petnum < 0);
            if(opt == 1) {
                insert(root, x);
                petnum--;
            }
            else {
                int pre = getPre(root, x);
                int nxt = getNxt(root, x);

                if(abs(pre - x) < abs(nxt - x)) {
                    del(pre);
                    ans = (ans + abs(pre - x)) % mod;
                    //debug(x);
                }
                else {
                    del(nxt);
                    ans = (ans + abs(nxt - x)) % mod;
                    //debug(x);
                }

                petnum++;
            }
        }
    }

    //dbg(root);
    printf("%d", ans);

    rmvTree(root);
}

数组版

const int maxn = 1e6 + 8;
const int mod = 1000000;
const int inf = 0x3f3f3f3f;
const int NIL = 0;
int n;

// == define tree ==

class Node {
public:
    int pa;
    int cld[2];
    int val, cnt;
} node[maxn];

inline int sgn(int u) {
    return node[node[u].pa].cld[1] == u;
}

int tot = 0;
int root;

int New(int val, int pa) {
    node[++tot].val = val;
    node[tot].pa = pa;
    node[tot].cnt = 1;
    return tot;
}

void build() {
    root = New(-inf, NIL);
    node[root].cld[1] = New(inf, root);
}

void dbg(int p) {
    if(node[p].cld[0]) dbg(node[p].cld[0]);

    printf("\n");
    debug(node[p].val);
    debug(node[node[p].pa].val);

    if(node[p].cld[1]) dbg(node[p].cld[1]);
}

// == define tree finished ==

// == rotate ==
inline void setc(int q, int d, int p) {
    if(p) node[p].pa = q;
    if(q) node[q].cld[d] = p;
    if(q == NIL) root = p;
}

inline void rot(int x, int d) {
    int y = node[x].pa, z = node[y].pa;

    if(z) setc(z, sgn(y), x);
    if(y) setc(y, d, node[x].cld[d^1]);
    setc(x, d^1, y);
}

inline void rot(int x) {
    return rot(x, sgn(x));
}
// == rotate finished ==

// == splay function ==
int splay(int p, const int to) {
    if(p == to) return p;

    while (node[p].pa != to) {
        if(node[p].pa == NIL) {
            root = p;
            break;
        }
        if(node[node[p].pa].pa == to) {
            rot(p);
            break;
        }
        else {
            int a = sgn(p), b = sgn(node[p].pa);
            rot((a^b ? p : node[p].pa), a);
            rot(p, b);
        }
    }
    return p;
}
// == splay finished ==

// == insert ==
void insert(const int p, int x) {
    int u = p;
    int pa = NIL;

    while (u && node[u].val != x) {
        pa = u;
        u = node[u].cld[x > node[u].val];
    }

    if(u) node[u].cnt++;
    else {
        if(pa) {
            u = New(x, pa);
            node[pa].cld[x > node[pa].val] = u;
        }
        else {
            u = New(x, NIL);
            root = u;
        }
    }

    splay(u, root);
}
// == insert finished ==

// == remove node ==
int Find(int x) {
    int u = root;
    while (true) {
        if(node[u].val == x) return u;
        if(node[u].cld[x > node[u].val] == 0) return NIL;
        u = node[u].cld[x > node[u].val];
    }
}

void _del(int x) {
    node[x].cld[0] = node[x].cld[1] = 0;
    node[x].pa = 0;
    node[x].val = node[x].cnt = 0;

    if(x == tot) tot--;
}

void del(int x) {
    int u = Find(x);
    if(u == NIL) return;

    splay(u, root);
    if(u != root) assert(node[u].pa == root);

    if(node[u].cnt > 1) {
        node[u].cnt--;
        return;
    }

    if(node[u].cld[0] == 0) {
        int d = sgn(u);
        setc(node[u].pa, d, node[u].cld[1]);
        _del(u);
    }
    else {
        int d = sgn(u);
        int pre = node[u].cld[0];
        while (node[pre].cld[1]) pre = node[pre].cld[1];

        splay(pre, u);
        assert(node[u].cld[0] == pre);

        setc(pre, 1, node[u].cld[1]);
        setc(node[u].pa, d, pre);
        _del(u);
    }
}
// == remove finished ==

// == precursor and successor ==
int getNxt(const int rt, int val) {
    int ans = inf;
    int p = rt;

    while (p) {
        if(val == node[p].val) {
            if(node[p].cnt >= 1) {
                ans = node[p].val;
                return ans;
            }
            if(node[p].cld[1]) {
                p = node[p].cld[1];
                while (node[p].cld[0]) p = node[p].cld[0];
                ans = node[p].val;
            }
            break;
        }
        if(node[p].val > val && node[p].val < ans) ans = node[p].val;
        p = val < node[p].val ? node[p].cld[0] : node[p].cld[1];
    }
    return ans;
}

int getPre(const int rt, int val) {
    int ans = -inf;
    int p = rt;

    while (p) {
        if(val == node[p].val) {
            if(node[p].cnt >= 1) {
                ans = node[p].val;
                return ans;
            }
            if(node[p].cld[0]) {
                p = node[p].cld[0];
                while (node[p].cld[1]) p = node[p].cld[1];
                ans = node[p].val;
            }
            break;
        }
        if(node[p].val < val && node[p].val > ans) ans = node[p].val;
        p = val < node[p].val ? node[p].cld[0] : node[p].cld[1];
    }
    return ans;
}
// == precursor and successor finished ==

int petnum = 0, ans = 0;

void init() {
    tot = 0;
    petnum = 0;
    ans = 0;
}


int main() {
    freopen("input.txt", "r", stdin);
    init();
    scanf("%d", &n);

    build();

    while (n--) {
        int opt;
        scanf("%d", &opt);
        int x;
        scanf("%d", &x);

        if(petnum == 0) {
            insert(root, x);
            if(opt == 0) petnum++;
            else petnum--;
        }
        else if(petnum > 0) {
            // all pet
            if(opt == 0) {
                insert(root, x);
                petnum++;
            }
            else {
                // adopt pet
                int pre = getPre(root, x);
                int nxt = getNxt(root, x);

                if(abs(pre - x) <= abs(nxt - x)) {
                    del(pre);
                    ans = (ans + abs(pre - x)) % mod;
                }
                else {
                    del(nxt);
                    ans = (ans + abs(nxt - x)) % mod;
                }

                petnum--;
            }
        }
        else {
            // all people
            if(opt == 1) {
                insert(root, x);
                petnum--;
            }
            else {
                int pre = getPre(root, x);
                int nxt = getNxt(root, x);

                if(abs(pre - x) < abs(nxt - x)) {
                    del(pre);
                    ans = (ans + abs(pre - x)) % mod;
                }
                else {
                    del(nxt);
                    ans = (ans + abs(nxt - x)) % mod;
                }

                petnum++;
            }
        }
    }
    printf("%d", ans);
}

splay处理区间问题

BZOJ1251

指针版

特别注意，因为有哨兵节点null的存在，所以 pushup() 的时候要小心
注意忽略 null 节点
编程技巧，使用static来定义哨兵节点

cld != null，才 pushup() 更新节点

const int maxn = 1e6 + 10;
const int inf = 0x3f3f3f3f;

// == tree structure ==
class Node {
public:
    static Node *null;
#define null Node::null
    Node *pa;
    Node *cld[2];

    int big, val, tag;
    int sz;
    bool rev;

    inline void pushdown() {
        if(tag) {
            _for(k, 0, 2) if(cld[k]) {
                cld[k]->tag += tag;
                cld[k]->val += tag;
                cld[k]->big += tag;
            }
            tag = 0;
        }
        if(rev) {
            _for(k, 0, 2) if(cld[k]) cld[k]->rev ^= 1;
            rev = 0;
            swap(cld[0], cld[1]);
        }
    }

    inline void pushup() {
        big = val;
        sz = 1;
        if(cld[0] != null) {
            big = max(big, cld[0]->big);
            sz += cld[0]->sz;
        }
        if(cld[1] != null) {
            big = max(big, cld[1]->big);
            sz += cld[1]->sz;
        }
    }

    inline int sgn() {
        return pa->cld[1] == this;
    }

    void setc(int d, Node *x) {
        cld[d] = x;
        x->pa = this;
    }

    void rot(int d) {
        Node *y = pa, *z = y->pa;
        z->setc(y->sgn(), this);
        y->setc(d, cld[d^1]);
        setc(d^1, y);

        y->pushup();
    }

    void rot() {
        rot(sgn());
    }

    Node *splay(const Node *to) {
        while (pa != to) {
            if(pa->pa == to) {
                rot();
                break;
            }
            else {
                int a = sgn(), b = pa->sgn();
                (a^b ? this : pa)->rot(a);
                rot(b);
            }
        }
        pushup();
        return this;
    }
} A[maxn];

Node *null = new Node();
typedef Node* T;
T NIL = new Node();
T root = &A[0];

T build(int l, int r) {
    if(l > r) return null;
    int mid = (l + r) >> 1;

    T p = &A[mid];

    p->cld[0] = build(l, mid - 1);
    p->cld[1] = build(mid + 1, r);
    p->val = p->rev = 0;
    if(p->cld[0]) p->cld[0]->pa = p;
    if(p->cld[1]) p->cld[1]->pa = p;
    p->pushup();

    return p;
}

void buildTree(int n) {
    root = build(1, n + 2);
    root->pa = NIL;
    NIL->pa = NULL;
    NIL->cld[0] = NULL;
    NIL->cld[1] = root;

    null->sz = 0;
    null->pa = NULL;
    null->val = -inf;
}

void levedbg(T rt) {
    queue<T> que;
    que.push(rt);
    int cnt = 1, nxtcnt = 0;
    int level = 1;

    while (!que.empty()) {
        T x = que.front(); que.pop();
        if(x != null && x != NIL && x) printf("%d(%d) ", x->val, x->sgn());
        cnt--;
        if(x == NULL) continue;

        if(x->cld[0] != null) que.push(x->cld[0]), nxtcnt++;
        if(x->cld[1] != null) que.push(x->cld[1]), nxtcnt++;

        if(cnt == 0) {
            printf("\n");
            cnt = nxtcnt;
            nxtcnt = 0;
        }
    }
}
// == tree finished ==

// == void dbg ==
void dbg(const T rt) {
    T u = rt;
    //u->pushdown();
    if(u->cld[0] != null && u->cld[0]) dbg(u->cld[0]);
    if(u != NIL && u != null && u) {
        printf("%d ", u->val);
    }
    if(u->cld[1] != null && u->cld[1]) dbg(u->cld[1]);
}
// == dbg finished ==

// == select kth ==
T select(const T rt, int k) {
    T u = rt;
    while (u != null) {
        if(u->cld[0]->sz == k - 1) return u;
        if(u->cld[0]->sz >= k) u = u->cld[0];
        else {
            k -= u->cld[0]->sz + 1;
            u = u->cld[1];
        }
        u->pushdown();
    }
    return u;
}

void change(int l, int r, int val) {
    T x1 = select(root, l - 1);
    T x2 = select(root, r + 1);
    //debug(x1->sz), debug(x2->sz); puts("");

    x1->splay(NIL), root = x1;
    //dbg(x1); puts("");
    x2->splay(x1);

    x2->cld[0]->val += val;
    x2->cld[0]->tag += val;
    x2->cld[0]->big += val;

    //dbg(x2->cld[0]); puts("");
}

void turn(int l, int r) {
    T x1 = select(root, l - 1);
    T x2 = select(root, r + 1);

    x1->splay(NIL), root = x1;
    x2->splay(x1);

    x2->cld[0]->rev ^= 1;
}

int query(int l, int r) {
    T x1 = select(root, l - 1);
    T x2 = select(root, r + 1);
    x1->splay(NIL), root = x1;
    x2->splay(x1);

    return x2->cld[0]->big;
}
// == select finished ==



int main() {
    freopen("input.txt", "r", stdin);
    int n, m;
    scanf("%d%d", &n, &m);

    buildTree(n);
    //levedbg(root);

    _for(i, 0, m) {
        int a, b, c, d;
        scanf("%d", &a);

        if(a == 1) {
            scanf("%d%d%d", &b, &c, &d);
            b++, c++;
            change(b, c, d);
            // dbg(root); puts("");
        }
        else if(a == 2) {
            scanf("%d%d", &b, &c);
            b++, c++;
            turn(b, c);
        }
        else {
            scanf("%d%d", &b, &c);
            b++, c++;
            printf("%d\n", query(b, c));
        }
    }
}

数组版

const int inf = 0x3f3f3f3f;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;

// == tree structure ==
const int NIL = 0;

class Node {
public:
    int pa;
    int cld[2];

    int big, val, tag;
    int sz;
    bool rev;

    void create(int _val, int _pa) {
        pa = _pa;
        big = val = _val;
        sz = 1;
        cld[0] = cld[1] = 0;
        tag = rev = 0;
    }
} T[maxn];

int root;

inline int sgn(int u) {
    return T[T[u].pa].cld[1] == u;
}

void pushup(int u) {
    T[u].big = T[u].val;
    T[u].sz = 1;

    if(T[u].cld[0]) {
        T[u].big = max(T[u].big, T[T[u].cld[0]].big);
        T[u].sz += T[T[u].cld[0]].sz;
    }

    if(T[u].cld[1]) {
        T[u].big = max(T[u].big, T[T[u].cld[1]].big);
        T[u].sz += T[T[u].cld[1]].sz;
    }
}

void pushdown(int u) {
    if(u == NIL) return;
    if(T[u].tag) {
        _for(k, 0, 2) if(T[u].cld[k]) {
            T[T[u].cld[k]].val += T[u].tag;
            T[T[u].cld[k]].tag += T[u].tag;
            T[T[u].cld[k]].big += T[u].tag;
        }

        T[u].tag = 0;
    }

    if(T[u].rev) {
        _for(k, 0, 2) {
            if(T[u].cld[k]) T[T[u].cld[k]].rev ^= 1;
        }

        swap(T[u].cld[0], T[u].cld[1]);
        T[u].rev = 0;
    }
}

int build(int l, int r) {
    if(l > r) return NIL;
    if(l == r) return l;

    int mid = (l + r) >> 1;
    int lson, rson;

    lson = T[mid].cld[0] = build(l, mid - 1);
    rson = T[mid].cld[1] = build(mid + 1, r);
    T[lson].pa = T[rson].pa = mid;

    pushup(mid);
    return mid;
}

void buildTree(int n) {
    T[1].create(-inf, NIL), T[n + 2].create(-inf, NIL);
    _rep(i, 2, n + 1) T[i].create(0, NIL);

    root = build(1, n + 2);
    T[root].pa = NIL;

    T[NIL].cld[1] = root;
    T[NIL].pa = 0;
    T[NIL].sz = 0;

    //assert(T[1].pa != NIL);
}
// == tree structure finsihed ==

// == void rotate and splay ==
inline void setc(int q, int d, int p) {
    if(p) T[p].pa = q;
    if(q) T[q].cld[d] = p;
    if(q == NIL) root = p;
}

inline void rot(int x, int d) {
    int y = T[x].pa, z = T[y].pa;

    setc(z, sgn(y), x);
    setc(y, d, T[x].cld[d^1]);
    setc(x, d^1, y);

    pushup(y);
}

inline void rot(int x) {
    return rot(x, sgn(x));
}

int splay(int p, const int to) {
    if(p == to) return p;

    while (T[p].pa != to) {
        int y = T[p].pa, z = T[y].pa;

        if(T[p].pa == NIL) {
            root = p;
            break;
        }
        if(T[T[p].pa].pa == to) {
            rot(p);
            break;
        }
        else {
            int a = sgn(p), b = sgn(T[p].pa);
            rot((a^b ? p : T[p].pa), a);
            rot(p, b);
        }
    }
    pushup(p);
    return p;
}
// == rotate and splay finished ==

// == select kth, return (k+1)th ==
int select(const int rt, int k) {
    int u = rt;
    pushdown(u);

    while (u && T[T[u].cld[0]].sz != k) {
        if(k < T[T[u].cld[0]].sz) u = T[u].cld[0];
        else {
            k -= T[T[u].cld[0]].sz + 1;
            u = T[u].cld[1];
        }
        pushdown(u);
    }
    return u;
}
// == select finsihed ==

// == void change ==
void change(int l, int r, int val) {
    int x = select(root, l - 1);
    int y = select(root, r + 1);

    splay(x, NIL);
    splay(y, x);

    T[T[y].cld[0]].val += val;
    T[T[y].cld[0]].tag += val;
    T[T[y].cld[0]].big += val;
}
// == change finsihed ==

void turn(int l, int r) {
    int x = select(root, l - 1);
    int y = select(root, r + 1);

    splay(x, NIL);
    splay(y, x);
    T[T[y].cld[0]].rev ^= 1;
}

int query(int l, int r) {
    int x = select(root, l - 1);
    int y = select(root, r + 1);
    splay(x, NIL);
    splay(y, x);
    return T[T[y].cld[0]].big;
}

// == void debug ==
void dbg(const int rt) {
    int u = rt;
    if(T[u].cld[0]) dbg(T[u].cld[0]);

    puts("");
    debug(T[u].sz);
    debug(T[u].val);
    debug(T[u].cld[0]);
    debug(T[u].cld[1]);

    if(T[u].cld[1]) dbg(T[u].cld[1]);
}
// == dbg

int main() {
    freopen("input.txt", "r", stdin);
    int n, m;
    scanf("%d%d", &n, &m);

    buildTree(n);
    _for(i, 0, m) {
        int a, b, c, d;
        scanf("%d", &a);

        //dbg(NIL);
        //puts("\n\n\n");
        if(a == 1) {
            scanf("%d%d%d", &b, &c, &d);
            change(b, c, d);
        }
        else if(a == 2) {
            scanf("%d%d", &b, &c);
            turn(b, c);
        }
        else {
            scanf("%d%d", &b, &c);
            printf("%d\n", query(b, c));
        }
    }
}

应用：反转序列

如果仅仅需要反转序列，在中序遍历的时候，记得下传延迟标记即可
BZOJ3223

void dfs(const int root) {
    int u = root;
    pushdown(u);

    if(T[u].cld[0]) dfs(T[u].cld[0]);
    if(T[u].val != -inf) printf("%d ", T[u].val);
    if(T[u].cld[1]) dfs(T[u].cld[1]);
}

另外注意设置哨兵的特殊值，避免输出哨兵

void buildTree(int n) {
    root = build(1, n + 2);
    root->pa = NIL;
    NIL->cld[0] = NULL;
    NIL->cld[1] = root;

    null->sz = 0;
    null->pa = NULL;

    A[1].val = -inf;
    A[n+2].val = -inf;
}

分裂和合并

UVA11922

const int maxn = 1e6 + 10;
const int inf = 0x3f3f3f3f;

// == tree structure ==
class Node {
public:
    static Node *null;
#define null Node::null
    Node* pa;
    Node* cld[2];

    int val, sz;
    bool rev;

    inline void pushdown() {
        if(rev)  {
            _for(k, 0, 2) if(cld[k]) cld[k]->rev ^= 1;
            swap(cld[0], cld[1]);
            rev = false;
        }
    }

    inline void pushup() {
        sz = 1;
        _for(k, 0, 2) if(cld[k] != null) sz += cld[k]->sz;
    }

    inline int sgn() {
        return pa->cld[1] == this;
    }

    void setc(int d, Node* x) {
        cld[d] = x;
        x->pa = this;
    }

    void rot(int d) {
        Node *y = pa, *z = y->pa;
        z->setc(y->sgn(), this);
        y->setc(d, cld[d^1]);
        setc(d^1, y);
        y->pushup();
    }
    void rot() {
        rot(sgn());
    }

    Node* splay(const Node* to) {
        while (pa != to) {
            if(pa->pa == to) {
                rot();
                break;
            }
            else {
                int a = sgn(), b = pa->sgn();
                (a^b ? this : pa)->rot(a);
                rot(b);
            }
        }
        pushup();
        return this;
    }
} A[maxn];

Node *null = new Node();
typedef Node* T;
T NIL = new Node();
T root = &A[0];

T build(int l, int r) {
    if(l > r) return null;
    int mid = (l + r) >> 1;
    T p = &A[mid];
    p->cld[0] = build(l, mid - 1);
    p->cld[1] = build(mid + 1, r);
    p->val = mid;

    if(p->cld[0]) p->cld[0]->pa = p;
    if(p->cld[1]) p->cld[1]->pa = p;
    p->pushup();

    return p;
}

void buildTree(int n) {
    root = build(1, n + 2);
    root->pa = NIL;
    NIL->pa = NULL;
    NIL->cld[1] = root;
    NIL->cld[0] = NULL;

    null->sz = 0;
    null->pa = NULL;
}
// == tree structure finished ==

// == debug ==
void dbg(T rt) {
    T u = rt;
    if(u->cld[0]) dbg(u->cld[0]);
    if(u != null) printf("cur: %d\n", u->val);
    if(u->cld[1]) dbg(u->cld[1]);
}

void leveldbg(T rt) {
    queue<T> que;
    que.push(rt);
    int cnt = 1, nxtcnt = 0;
    int level = 1;
    while (!que.empty()) {
        T x = que.front();
        que.pop();
        if(x != null && x != NIL && x) printf("%d(%d) ", x->val, x->sgn());
        cnt--;
        if(x == NULL) continue;

        if(x->cld[0] != null) que.push(x->cld[0]), nxtcnt++;
        if(x->cld[1] != null) que.push(x->cld[1]), nxtcnt++;

        if(cnt == 0) {
            //printf("level: %d\n", level++);
            puts("");
            cnt = nxtcnt;
            nxtcnt = 0;
        }
    }
}
// == debug finished ==

// == select kth ==
T select(const T rt, int k) {
    T u = rt;
    while (u != null) {
        if(u->cld[0]->sz == k - 1) return u;
        if(u->cld[0]->sz >= k) u = u->cld[0];
        else {
            k -= u->cld[0]->sz + 1;
            u = u->cld[1];
        }
        u->pushdown();
    }
    return u;
}
// == select finsihed ==

void test() {
    int a, b;
    scanf("%d%d", &a, &b);
    T u = select(root, a);
    debug(u->val);
    if(u != null) u->splay(NIL);
    root = u;
    leveldbg(root);
}


// == reverse ==
inline void turn(int x1, int x2) {
    T L = select(root, x1 - 1), R = select(root, x2 + 1);
    L->splay(NIL), root = L;
    R->splay(root);

    T goal = R->cld[0];
    goal->rev ^= 1;
    R->cld[0] = null;
    R->pushup();
    root->pushup();

    T t1 = select(root, root->sz);
    T t2 = select(root, root->sz-1);
    t2->splay(NIL), root = t2;
    t1->splay(root);

    t1->cld[0] = goal;
    goal->pa = t1;

    t1->pushup();
    root->pushup();
}
// == reverse finsihed ==

vector<int> ans;
void dfs(T r, int n) {
    r->pushdown();
    if(r->cld[0] != null) dfs(r->cld[0], n);
    if(r->val != 1 && r->val != n + 2) printf("%d\n", r->val - 1);
    if(r->cld[1] != null) dfs(r->cld[1], n);
}

int main() {
    freopen("input.txt", "r", stdin);
    int n, m;
    scanf("%d%d", &n, &m);
    buildTree(n);
    //leveldbg(root);

    while (m--) {
        int x1, x2;
        scanf("%d%d", &x1, &x2);
        x1++, x2++;
        turn(x1, x2);
    }
    dfs(root, n);
}