kkogoro

平衡树模板
平衡树模板要注意getKth时如果没有这个元素的边界处理问题Treap普通平衡树#include <iost...
扫描右侧二维码阅读全文
20
2018/11

平衡树模板

平衡树模板

要注意getKth时如果没有这个元素的边界处理问题

Treap

普通平衡树

#include <iostream>
#include <ctime>
#include <cstdlib>
#include <cstdio>


inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}


struct Treap {
    static const int INF = 100000000;
    static const int MAXN = 100007;
    struct Node {
        int lc, rc, num, cnt, sum, dat;    
    } node[MAXN];
    int cntNode, root;
#define L(x) node[x].lc
#define R(x) node[x].rc
#define V(x) node[x].num
#define C(x) node[x].cnt
#define S(x) node[x].sum
#define D(x) node[x].dat
    inline int newNode(int val) {
        ++cntNode;
        V(cntNode) = val;
        D(cntNode) = std::rand();
        C(cntNode) = S(cntNode) = 1;
        return cntNode;
    }
    inline void pushUP(int cur) {
        S(cur) = S(L(cur)) + S(R(cur)) + C(cur);
        return;
    }
    inline void build() {
        root = newNode(-INF);
        newNode(INF);
        R(root) = 2;
        pushUP(root);
        return;
    }
    inline void zig(int &p) {
        int q = L(p);
        L(p) = R(q), R(q) = p, p = q;
        pushUP(R(p));
        pushUP(p);
        return;    
    }
    inline void zag(int &p) {
        int q = R(p);
        R(p) = L(q), L(q) = p, p = q;
        pushUP(L(p));
        pushUP(p);
        return;
    }
    void insert(int &p, int val) {
        if (!p) {
            p = newNode(val);
            return;    
        }
        if (val == V(p)) {
            ++C(p);
            pushUP(p);
            return;    
        }
        if (val < V(p)) {
            insert(L(p), val);
            if (D(L(p)) > D(p)) {
                zig(p);    
            }
        }
        else {
            insert(R(p), val);
            if (D(R(p)) > D(p)) {
                zag(p);    
            }
        }
        pushUP(p);
        return;
    }
    void erase(int &p, int val) {
        if (!p) {
            return;
        }
        
        if (val == V(p)) {
            if (C(p) > 1) {
                --C(p);
            }
            else if (L(p) || R(p)) {
                if (!R(p) || D(L(p)) > D(R(p))) {
                    zig(p);
                    erase(R(p), val);
                }
                else {
                    zag(p);
                    erase(L(p), val);
                }
            }
            else {
                p = 0;
            }
        }
        else {
            val < V(p) ? erase(L(p), val) : erase(R(p), val);    
        }
        pushUP(p);
        return;
    }
    int getRank(int &p, int val) {
        if (!p) {
            return 0;
        }
        if (val == V(p)) {
            return S(L(p)) + 1;    
        }
        if (val < V(p)) {
            return getRank(L(p), val);
        }
        return S(L(p)) + C(p) + getRank(R(p), val);
    }
    int getNum(int &p, int rank) {
        if (!p) {
            return INF;
        }
        if (S(L(p)) >= rank) {
            return getNum(L(p), rank);    
        }
        if (S(L(p)) + C(p) >= rank) {
            return V(p);
        }
        return getNum(R(p), rank - S(L(p)) - C(p));
    }
    int getPre(int val) {
        int ans = 0, p = root;
        while (p > 0) {
            if (val > V(p)) {
                ans = p;
                p = R(p);    
            }
            else {
                p = L(p);
            }
        }
        return V(ans);
    }
    int getNext(int val) {
        int ans = 0, p = root;
        while (p > 0) {
            if (val < V(p)) {
                ans = p;
                p = L(p);
            }
            else {
                p = R(p);
            }
        }
        return V(ans);
    }
#undef L
#undef R
#undef V
#undef C
#undef S
#undef D
} tree_1;


namespace BST {
    inline void init() {
        tree_1.build();
        return;
    }
    inline void insert(int val) {
        tree_1.insert(tree_1.root, val);
        return;
    }
    inline void erase(int val) {
        tree_1.erase(tree_1.root, val);
        return;
    }
    inline int getRank(int val) {
        return tree_1.getRank(tree_1.root, val) - 1;
    }
    inline int getNum(int rank) {
        return tree_1.getNum(tree_1.root, rank + 1);
    }
    inline int getPre(int val) {
        return tree_1.getPre(val);
    }
    inline int getNext(int val) {
        return tree_1.getNext(val);    
    }
}


int main() {
    srand(time(NULL));
    
    BST::init();
    int n = read();
    while (n--) {
        int opt = read();
        int x = read();
        switch(opt) {
            case 1 :
                BST::insert(x);
                break;
            case 2 :
                BST::erase(x);
                break;
            case 3 :
                printf("%d\n", BST::getRank(x));
                break;
            case 4 :
                printf("%d\n", BST::getNum(x));
                break;
            case 5 :
                printf("%d\n", BST::getPre(x));
                break;
            case 6 :
                printf("%d\n", BST::getNext(x));
                break;
        }
    }
    return 0;
}

非严格前驱

int getPre(int val) {
    int ans = 0, p = root;
    while (p > 0) {
        if (val > V(p)) {
            ans = p;
            p = R(p);    
        }
        else {
            if (val == V(p)) {
                ans = p;
                break; //break很重要!
            }
            p = L(p);
        }
    }
    return V(ans);
}

Splay

文艺平衡树

#include <iostream>
#include <cstdio>


inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}



const int MAXN = 100007;


class SplayNode {
    int fa, ch[2], sum, tag;
    friend class Splay;
} node[MAXN];
int cntNode;
class Splay {
#define F(x) node[x].fa
#define L(x) node[x].ch[0]
#define R(x) node[x].ch[1]
#define H(x, y) node[x].ch[y]
#define T(x) node[x].tag
#define S(x) node[x].sum
    private :
        int root;
        inline void pushUP(int x) {
            if (x) S(x) = S(L(x)) + S(R(x)) + 1;
            return;
        }
        inline void pushDOWN(int x) {
            if (!x) return;
            if (T(x)) {
                std::swap(L(x), R(x));
                if (L(x)) T(L(x)) ^= 1;
                if (R(x)) T(R(x)) ^= 1;
                T(x) = 0;
            }
            return;
        }
        inline int indent(int x) {
            return R(F(x)) == x;
        }
        inline void setRoot(int x) {
            root = x, F(x) = 0;
            return;
        }
        inline void connect(int x, int f, int how) {
            H(f, how) = x, F(x) = f;
            return;
        }
        inline void rotate(int x) {
            int y = F(x), yson = indent(x);
            if (y == root) setRoot(x);
            else connect(x, F(y), indent(y));
            connect(H(x, !yson), y, yson);
            connect(y, x, !yson);
            pushUP(y);
            pushUP(x);
            return;
        }
        inline void splay(int x, int r) {
            for (int y; (y = F(x)) != r; rotate(x))
                if (F(y) != r) rotate(indent(x) == indent(y) ? y : x);
            return;
        }
        inline int getKth(int k) {
            int p = root;
            while (1) {
                if (!p) return 0;
                pushDOWN(p);
                if (S(L(p)) >= k) p = L(p);
                else if (S(L(p)) + 1 == k) return p;
                else k -= S(L(p)) + 1, p = R(p);
            }
        }
        int build(int l, int r, int f) {
            if (l > r) return 0;
            int mid = (l + r) >> 1;
            F(mid) = f;
            L(mid) = build(l, mid - 1, mid);
            R(mid) = build(mid + 1, r, mid);
            pushUP(mid);
            return mid;
        }
        void dfs(int p, int n) {
            pushDOWN(p);
            if (L(p)) dfs(L(p), n);
            if (p > 1 && p < n + 2) printf("%d ", p - 1);
            if (R(p)) dfs(R(p), n);
            return;
        }
    public :
        inline void rever(int l, int r) {
            int x = getKth(l);
            int y = getKth(r + 2);
            splay(x, 0);
            splay(y, root);
            T(L(y)) ^= 1;
            return;
        }
        void init(int n) {
            setRoot(build(1, n + 2, 0));
            return;
        }
        void print(int n) {
            dfs(root, n);
            return;
        }
#undef F
#undef L
#undef R
#undef H
#undef T
#undef S
} tree;


int main() {
    int n = read();
    int m = read();
    tree.init(n);
    for (int i = 1; i <= m; ++i) {
        int l = read();
        int r = read();
        tree.rever(l, r);    
    }
    tree.print(n);
    return 0;
}

普通平衡树

#include <iostream>
#include <cstdio>


inline int read() {
    int x = 0, f =  1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}


const int MAXN = 100007;
const int INF = 1000000000;


class SplayNode {
    int fa, val, cnt, sum, ch[2];
    friend class Splay;
} node[MAXN];
int cntNode;
class Splay {
#define F(x) node[x].fa
#define V(x) node[x].val
#define C(x) node[x].cnt
#define S(x) node[x].sum
#define L(x) node[x].ch[0]
#define R(x) node[x].ch[1]
#define H(x, y) node[x].ch[y]
    private :
        int root;
        inline int newNode(int val, int f) {
            ++cntNode;
            V(cntNode) = val, C(cntNode) = S(cntNode) = 1, F(cntNode) = f;
            return cntNode;
        }
        inline void setRoot(int x) {
            root = x, F(x) = 0;
            return;
        }
        inline void pushUP(int x) {
            if (x) S(x) = S(L(x)) + S(R(x)) + C(x);
            return;
        }
        inline void connect(int x, int f, int how) {
            H(f, how) = x, F(x) = f;
            return;
        }
        inline int indent(int x) {
            return R(F(x)) == x;
        }
        inline void rotate(int x) {
            int y = F(x), yson = indent(x);
            if (y == root) setRoot(x);
            else connect(x, F(y), indent(y));
            connect(H(x, !yson), y, yson);
            connect(y, x, !yson);
            pushUP(y);
            pushUP(x);
            return;
        }
        inline void splay(int x, int r) {
            if (x == r) return;
            for (int y; (y = F(x)) != r; rotate(x))
                if (F(y) != r) rotate(indent(x) == indent(y) ? y : x);
            return;
        }

    public :
        inline void insert(int val) {
            int p = root;
            if (!root) {
                setRoot(newNode(val, 0)); 
                return;
            }
            while (1) {
                ++S(p);
                if (V(p) == val) {
                    ++C(p);
                    splay(p, 0);
                    break;
                }
                int to = val > V(p);
                if (H(p, to) == 0) {
                    int born = newNode(val, p);
                    H(p, to) = born;
                    splay(born, 0);
                    break;
                }
                p = H(p, to);
            }
            return;
        }
        inline int find(int val) {
            int p = root;
            while (1) {
                if (p == 0) return 0;
                if (V(p) == val) {
                    splay(p, 0);
                    return p;
                }
                p = H(p, val > V(p));
            }
        }
        inline void erase(int val) {
            int p = find(val);
            if (p == 0) return;
            if (C(p) > 1) {--C(p), --S(p);}
            else if (L(p) == 0 && R(p) == 0) setRoot(0);
            else if (L(p) == 0) setRoot(R(p));
            else {
                int left = L(p);
                while (R(left)) left = R(left);
                splay(left, root);
                connect(R(root), left, 1);
                setRoot(left);
                pushUP(left);
            }
            return;
        }
        inline int getRank(int val) {
            return S(L(find(val))) + 1;
        }
        inline int getKth(int k) {
            int p = root;
            while (1) {
                if (S(L(p)) >= k) p = L(p);
                else if (S(L(p)) + C(p) >= k) break;
                else k -= S(L(p)) + C(p), p = R(p);
            }
            splay(p, 0);
            return V(p);
        }
        inline int lower(int val) {
            int p = root, ans = -INF;
            while (p) {
                if (V(p) < val) ans = std::max(ans, V(p));
                p = H(p, val > V(p));
            }
            return ans;
        }
        inline int upper(int val) {
            int p = root, ans = INF;
            while (p) {
                if (V(p) > val) ans = std::min(ans, V(p));
                p = H(p, val >= V(p));
            }
            return ans;
        }
#undef F
#undef V
#undef C
#undef S
#undef L
#undef R
#undef H
};


Splay tree;


int main() {
    int n = read();
    while (n--) {
        int opt = read();
        int x = read();
        switch (opt) {
            case 1 :
                tree.insert(x);
                break;
            case 2 :
                tree.erase(x);
                break;
            case 3 :
                printf("%d\n", tree.getRank(x));
                break;
            case 4 :
                printf("%d\n", tree.getKth(x));
                break;
            case 5 :
                printf("%d\n", tree.lower(x));
                break;
            case 6 :
                printf("%d\n", tree.upper(x));
                break;
        }
    }
    return 0;
}

非严格前驱

inline int lower(int x) {
    int p = root, ans = -INF;
    while (p) {
        if (V(p) <= x) ans = std::max(ans, V(p));
        p = H(p, x <= V(p) ? 0 : 1);
    }
    return ans;
}

fhq Treap

普通平衡树

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cstdlib>


inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar ();
    }
    return x * f;
}


const int MAXN = 100007;
typedef std::pair<int, int> PII;


struct TreapNode {
    int ch[2], size, val, key;
} node[MAXN];
int cntNode;
struct fhqTreap {
#define L(x) node[x].ch[0]
#define R(x) node[x].ch[1]
#define S(x) node[x].size
#define V(x) node[x].val
#define K(x) node[x].key
    int root;
    inline int newNode(const int &val) {
        TreapNode *it = &node[++cntNode];
        it->val = val, it->size = 1, it->key = std::rand(), it->ch[0] = it->ch[1] = 0;
        return cntNode;
    }
    inline void pushUP(const int &x) {
        if (x) S(x) = S(L(x)) + S(R(x)) + 1;
        return;
    }
    void split(int now, int &Ln, int &Rn, const int &val) {
        if (!now) return void(Ln = Rn = 0);
        if (V(now) <= val) {
            Ln = now;
            split(R(now), R(Ln), Rn, val);
            pushUP(Ln);
        }
        else {
            Rn = now;
            split(L(now), Ln, L(Rn), val);
            pushUP(Rn);
        }
        return;
    }
    int merge(const int &Ln, const int &Rn) {
        if (!Ln || !Rn) return Ln + Rn;
        if (K(Ln) < K(Rn)) {
            R(Ln) = merge(R(Ln), Rn);
            pushUP(Ln);
            return Ln;
        }
        else {
            L(Rn) = merge(Ln, L(Rn));
            pushUP(Rn);
            return Rn;
        }
    }
    inline void insert(const int &val) {
        int x, y;
        split(root, x, y, val);
        root = merge(merge(x, newNode(val)), y);
        return;
    }
    inline void erase(const int &val) {
        int x, y, z;
        split(root, x, z, val);
        split(x, x, y, val - 1);
        y = merge(L(y), R(y));
        root = merge(merge(x, y), z);
        return;
    }
    inline PII getKth(int rank) {
        int p = root;
        while (1) {
            if (rank <= S(L(p))) p = L(p);
            else if (rank == S(L(p)) + 1) return PII(V(p), p);
            else rank -= S(L(p)) + 1, p = R(p);
        }
    }
    inline PII getKth(int p, int rank) {
        while (1) {
            if (rank <= S(L(p))) p = L(p);
            else if (rank == S(L(p)) + 1) return PII(V(p), p);
            else rank -= S(L(p)) + 1, p = R(p);
        }
    }
    inline int getRank(const int &val) {
        int x, y, ret;
        split(root, x, y, val - 1);
        ret = S(x) + 1;
        root = merge(x, y);
        return ret;
    }
    inline int lower(const int &val) {
        int x, y, ret;
        split(root, x, y, val - 1);
        if (x) ret = getKth(x, S(x)).first;
        else ret = -2147483647;
        root = merge(x, y);
        return ret;
    }
    inline int upper(const int &val) {
        int x, y, ret;
        split(root, x, y, val);
        if (y) ret = getKth(y, 1).first;
        else ret = 2147483647;
        root = merge(x, y);
        return ret;
    }
#undef L
#undef R
#undef K
#undef V
#undef S
} tree;


int main() {
    srand(time(NULL));
    int n = read();
    for (int i = 1; i <= n; ++i) {
        int opt = read();
        int x = read();
        switch (opt) {
            case 1 :
                tree.insert(x);
                break;
            case 2 :
                tree.erase(x);
                break;
            case 3 :
                printf("%d\n", tree.getRank(x));
                break;
            case 4 :
                printf("%d\n", tree.getKth(x).first);
                break;
            case 5 :
                printf("%d\n", tree.lower(x));
                break;
            case 6 :
                printf("%d\n", tree.upper(x));
                break;
        }
    }
    return 0;
}

文艺平衡树

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cstdio>


inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();    
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}


const int MAXN = 100007;


struct FhqTreap {
    struct Node {
        int size, tag, ch[2], key;
    } node[MAXN];
#define L(x) node[x].ch[0]
#define R(x) node[x].ch[1]
#define K(x) node[x].key
#define S(x) node[x].size
#define T(x) node[x].tag
    int cntNode, root;
    inline int newNode() {
        Node *it = &node[++cntNode];
        it->key = std::rand(), it->size = 1;
        return cntNode;
    }
    inline void pushUP(const int &x) {
        if (x) S(x) = S(L(x)) + S(R(x)) + 1;
        return;
    }
    inline void pushDOWN(const int &x) {
        if (x && T(x)) {
            T(x) = 0;
            std::swap(L(x), R(x));
            if (L(x)) T(L(x)) ^= 1;    
            if (R(x)) T(R(x)) ^= 1;
        }
        return;
    }
    void split(int now, int &Ln, int &Rn, const int &val) {
        if (!now) {
            Ln = Rn = 0;
            return;    
        }
        pushDOWN(now);
        
        if (S(L(now)) < val) {
            Ln = now;
            split(R(now), R(Ln), Rn, val - S(L(now)) - 1);    
        }
        else {
            Rn = now;
            split(L(now), Ln, L(Rn), val);
        }
        pushUP(now);
        return;
    }
    int merge(const int &Ln, const int &Rn) {
        if (Ln == 0 || Rn == 0) return Ln + Rn;
        if (K(Ln) < K(Rn)) {
            pushDOWN(Ln);
            R(Ln) = merge(R(Ln), Rn);
            pushUP(Ln);
            return Ln;
        }
        else {
            pushDOWN(Rn);
            L(Rn) = merge(Ln, L(Rn));
            pushUP(Rn);
            return Rn;
        }
    }
    inline void print(const int &x) {
        pushDOWN(x);
        if (L(x)) print(L(x));
        printf("%d ", x);
        if (R(x)) print(R(x));
        return;
    }
    inline void build(const int &n) {
        for (int i = 1; i <= n; ++i) {
            root = merge(root, newNode());    
        }
        return;
    }
    inline void rever(const int &l, const int &r) {
        int x, y, z;
        split(root, x, y, l - 1);
        split(y, y, z, r - l + 1);
        T(y) ^= 1;
        root = merge(merge(x, y), z);
        return;
    }
#unfine L
#unfine R
#unfine K
#unfine S
#unfine T
} tree;


int main() {
    srand(time(NULL));
    int n = read();
    int m = read();
    tree.build(n);
    for (int i = 1; i <= m; ++i) {
        int l = read();
        int r = read();
        tree.rever(l, r);
    }
    tree.print(tree.root);
    return 0;
}

可持久化平衡树

使用非旋式Treap实现的可持久化平衡树

与普通非旋式Treap的区别在于对原来需要改变一些节点的父子关系的时候在可持久化中需要新建节点

并且在查询操作中不需要将剖开的树合并回去,因为分裂的时候已经复制新节点了

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <ctime>
#include <cstdlib>


const int MAXN = 500007;


inline int read() {
    int x = 0, f = 1;
    char ch =getchar();
    while (ch < '0' ||ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}


namespace FhqTreap {
#define L(x) node[x].lc
#define R(x) node[x].rc
#define K(x) node[x].key
#define V(x) node[x].val
#define S(x) node[x].size
    struct Node {
        int lc, rc, val, key, size;
    } node[MAXN * 50];
    int cntNode, root[MAXN];
    inline int copyNode(const int &x) {
        node[++cntNode] = node[x];
        return cntNode;
    }
    inline int newNode(const int &val) {
        Node *it = &node[++cntNode];
        it->val = val, it->size = 1, it->lc = it->rc = 0, it->key = std::rand();
        return cntNode;
    }
    inline void pushUP(const int &x) {
        if (x) S(x) = S(L(x)) + S(R(x)) + 1;
        return;
    }
    void split(int now, int &Ln, int &Rn, const int &val) {
        if (!now) return void(Ln = Rn = 0);
        if (V(now) <= val) {
            Ln = copyNode(now);
            split(R(now), R(Ln), Rn, val);
            pushUP(Ln);
        }
        else {
            Rn = copyNode(now);
            split(L(now), Ln, L(Rn), val);
            pushUP(Rn);
        }
        return;
    }
    int merge(const int &Ln, const int &Rn) {
        if (!Ln || !Rn) return Ln + Rn;
        if (K(Ln) < K(Rn)) {
            int ret = copyNode(Ln);
            R(ret) = merge(R(ret), Rn);
            pushUP(ret);
            return ret;
        }
        else {
            int ret = copyNode(Rn);
            L(ret) = merge(Ln, L(ret));
            pushUP(ret);
            return ret;
        }
    }
    inline void insert(const int &version, const int &val) {
        int x, y;
        split(root[version], x, y, val);
        root[version] = merge(merge(x, newNode(val)), y);
        return;
    }
    inline void erase(const int &version, const int &val) {
        int x, y, z;
        split(root[version], x, z, val);
        split(x, x, y, val - 1);
        y = merge(L(y), R(y));
        root[version] = merge(merge(x, y), z);
        return;
    }
    inline int getRank(const int &version, const int &val) {
        int x, y, ret;
        split(root[version], x, y, val - 1);
        ret = S(x) + 1;
        return ret;
    }
    inline int getKth(int p, int rank) {
        while (1) {
            if (rank <= S(L(p))) p = L(p);
            else if (rank == S(L(p)) + 1) return V(p);
            else rank -= S(L(p)) + 1, p = R(p);
        }
    }
    inline int getPre(const int &version, const int &val) {
        int x, y, ret;
        split(root[version], x, y, val - 1);
        if (!x) ret = -2147483647;
        else ret = getKth(x, S(x));
        return ret;
    }
    inline int getNext(const int &version, const int &val) {
        int x, y, ret;
        split(root[version], x, y, val);
        if (!y) ret = 2147483647;
        else ret = getKth(y, 1);
        return ret;
    }
#undef L
#undef R
#undef S
#undef K
#undef V
}


int main() {
    srand(time(NULL));
    int n = read();
    for (int i = 1; i <= n; ++i) {
        int base_version = read();
        int opt = read();
        int x = read();
        FhqTreap::root[i] = FhqTreap::root[base_version];
        switch(opt) {
            case 1 :
                FhqTreap::insert(i, x);
                break;
            case 2 :
                FhqTreap::erase(i, x);
                break;
            case 3 :
                printf("%d\n", FhqTreap::getRank(i, x));
                break;
            case 4 :
                printf("%d\n", FhqTreap::getKth(FhqTreap::root[i], x));
                break;
            case 5 :
                printf("%d\n", FhqTreap::getPre(i, x));
                break;
            case 6 :
                printf("%d\n", FhqTreap::getNext(i, x));
                break;
        }
    }
    return 0;
}
Last modification:March 11th, 2019 at 10:21 am

Leave a Comment