伸展树

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e5+5;
namespace Splay_Tree{
    //维护序列的伸展树,
    //如果维护序列(位置)的话,可以用merge函数来合并平衡树(大小关系已知,大小关系就是位置关系)
    //如果维护的是值本身,就要用 dsu_merge进行启发式合并(任何时候不要用merge) 
    struct Node {
        int v = 0;//该节点值 
        int fa = 0;
        int ch[2] = {0, 0};
        int siz = 0;//子树大小 
        int max = 0;//子树最大值 
        int rev = 0;//翻转标记 
    };
    Node tree[maxn];
    bool findd(int x){
        return tree[tree[x].fa].ch[0] != x;
    }
    void connect(int x, int fa, int son){ // 把x放到fa的左子树,保证fa的左子树为空,否则要把最值spaly到根。
        if (x) {
            tree[x].fa = fa;
        }
        if (fa) {
            tree[fa].ch[son] = x;
        }
    }
    void rev(int &x) {//序列反正,一般来说不维护序列用不到这个 
        tree[x].rev ^= 1;
        swap(tree[x].ch[0], tree[x].ch[1]);
    }
    void pushdown(int x){//下传翻转标记
        if (tree[x].rev) {
            int ls = tree[x].ch[0], rs = tree[x].ch[1];
            rev(ls);
            rev(rs);
            tree[x].rev = 0;
        }
    }
    void pushup(int x){
        if (x) {
            tree[x].siz = tree[tree[x].ch[0]].siz + tree[tree[x].ch[1]].siz + 1;
            tree[x].max = std::max(tree[x].v, std::max(tree[tree[x].ch[0]].max, tree[tree[x].ch[1]].max));
        }
    }
    void rotate(int x)
    {
        int y = tree[x].fa;
        int r = tree[y].fa;
        int yson = findd(x);
        int rson = findd(y);
        int b = tree[x].ch[!yson];
        connect(b, y, yson);
        connect(y, x, !yson);
        connect(x, r, rson);
        pushup(y);
        pushup(x);
    }
    void splay(int x, int to){//把x上旋到to位置 
        to = tree[to].fa;
        while (tree[x].fa != to) {
            int y = tree[x].fa;
            if (tree[y].fa == to) {
                rotate(x);
            } else if (findd(x) == findd(y)) {
                rotate(y);
                rotate(x);
            } else {
                rotate(x);
                rotate(x);
            }
        }
    }
    int arank(int x, int root){//以root为根的树,拍第x名的是谁,第x名充当新根并返回 
        int now = root;
        while (true) {
            pushdown(now);
            int used = tree[now].siz - tree[tree[now].ch[1]].siz;
            if (x == used) {
                splay(now, root);
                return now;
            }
            if (x < used) {
                now = tree[now].ch[0];
            } else {
                x -= used;
                now = tree[now].ch[1];
            }
        }
    }
    int merge(int x, int y){//把x树与y树合并,保证x都比y小或者大。
        if (!x) {
            return y;
        }
        if (!y) {
            return x;
        }
        pushdown(x);
        pushdown(y);
        y = arank(1, y);
        connect(x, y, 0);
        pushup(y);
        return y;
    }

    int insert(int x, int y){//把y 
        int now = x;
        while(now){
            pushdown(now);
            int son = tree[y].v > tree[now].v;//注意,我这里是左子树小于右子树 
            if(!tree[now].ch[son]){
                connect(y, now, son);
                pushup(now);
                splay(y, x);
                return y;
            }
            now = tree[now].ch[son];
        }
        return y; 
    }
    int dsu_on_merge(int x, int y){
        pushdown(y);
        if(tree[y].ch[0]) x = dsu_on_merge(x, tree[y].ch[0]);
        if(tree[y].ch[1]) x = dsu_on_merge(x, tree[y].ch[1]);
        tree[y].siz = 1;
        tree[y].ch[0] = tree[y].ch[1] = 0;
        tree[y].max = tree[y].v;
        return insert(x, y);
    }
    int dsu_merge(int x, int y){//把平衡树y与x启发式合并 ,返回新根 
        if(tree[x].siz < tree[y].siz) swap(x, y);
        return dsu_on_merge(x, y);
    }

    void split(int t, int k, int& x, int& y){//把以t为根的树分成左边k个,右边n-k个,左树根为x,右树根为y
        if(!k){
            x = 0;
            y = t;
            return;
        }
        pushdown(t);
        x = arank(k, t);
        y = tree[x].ch[1];
        tree[y].fa = 0;
        tree[x].ch[1] = 0;
        pushup(x);
    }
    int getlen(int p, int x){//以p为根的树,x在其中拍第几名,没有的话返回0
        pushdown(p);
        if (!p) {
            return 0;
        } else if (tree[tree[p].ch[0]].max > x) {
            return getlen(tree[p].ch[0], x);
        } else if (tree[p].v > x) {
            return tree[tree[p].ch[0]].siz;
        } else {
            return getlen(tree[p].ch[1], x) + tree[tree[p].ch[0]].siz + 1;
        }
    }
}