Treap(可持久化）

Treap 腹黑猫 数据结构

#include "iostream"
#include "cstdlib"
using namespace std;
struct Node{
    Node* Child[2];
    int Key;
    int Priority;
    int Size;
    void Maintain(){
        Size = 1;
        if (Child[0] != NULL) Size += Child[0]->Size;
        if (Child[1] != NULL) Size += Child[1]->Size;
    }
};
Node* Root = NULL;
int Size(Node* A){
    return (A == NULL ? 0 : A->Size); 
}
Node* Merge(Node* A, Node* B){
    if (A == NULL) return B;
    if (B == NULL) return A;
    if (A->Priority < B->Priority){
        A->Child[1] = Merge(A->Child[1], B);
        A->Maintain();
        return A;
    }else{
        B->Child[0] = Merge(A, B->Child[0]);
        B->Maintain();
        return B;
    }
}
pair<Node*, Node*> Split(Node* A, int K){
    if (A == NULL) return pair<Node*, Node*>(NULL, NULL);
    pair<Node*, Node*> DoubleRoot;
    if (K <= Size(A->Child[0])){
        DoubleRoot = Split(A->Child[0], K);
        A->Child[0] = DoubleRoot.second;
        A->Maintain();
        DoubleRoot.second = A;
    }else{
        DoubleRoot = Split(A->Child[1], K - Size(A->Child[0]) - 1);
        A->Child[1] = DoubleRoot.first;
        A->Maintain();
        DoubleRoot.first = A;
    }
    return DoubleRoot;
}
int FindKth(int K){ //第K小 
    pair<Node*, Node*> Left = Split(Root, K - 1);
    pair<Node*, Node*> Right = Split(Left.second, 1);
    Node* Kth = Right.first;
    Root = Merge(Merge(Left.first, Kth), Right.second);
    return Kth->Key;
}
int Rank(Node* Top, int Key){ //Key为第几大 
    if (Top == NULL) return 0;
    return (Key < Top->Key ? Rank(Top->Child[0], Key) : Rank(Top->Child[1], Key) + Size(Top->Child[0]) + 1);
}
void Insert(int Key){
    Node* NewNode = new Node();
    NewNode->Key = Key;
    NewNode->Priority = rand();
    NewNode->Child[0] = NewNode->Child[1] = NULL;
    NewNode->Maintain();
    int Pos = Rank(Root, Key);
    pair<Node*, Node*> DoubleRoot = Split(Root, Pos);
    Root = Merge(Merge(DoubleRoot.first, NewNode), DoubleRoot.second);
}
void Remove(int Key){
    int K = Rank(Root, Key);
    pair<Node*, Node*> Left = Split(Root, K - 1);
    pair<Node*, Node*> Right = Split(Left.second, 1);
    Root = Merge(Left.first, Right.second);
}
void Modify(int KeyBefore, int KeyAfter){
    Remove(KeyBefore);
    Insert(KeyAfter);
}
int main(int argc, char const *argv[]){
    Insert(100);
    Insert(500);
    Insert(300);
    Insert(200);
    Remove(100);
    cout << Rank(Root, 300);
    return 0;
}