Q

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
template<typename Key, typename Value>
class SplayBST{
    struct Node{
        Key key;
        Value value;
        Node *left, *right;
        Node(){}
        Node(Key key, Value value){
            this->key = key, this->value = value;
            this->left  = this->right  = NULL;
        }
    };
// Get value
public:
    Node* root = NULL;

    Value get(Key key){
        root = splay(root, key);
        if (root->key == key){
            return root->value;
        } else {
            return NULL;
        }
    }
// insert
    void put(Key key, Value value){
        if (root == NULL){
            root = new Node(key, value);
            return;
        }
        root = splay(root, key);
        if (key < root->key){
            Node* n = new Node(key, value);
            n->left = root->left;
            n->right= root;
            root->left = NULL;
            root = n;
        } else if (key > root->key){
            Node* n = new Node(key, value);
            n->right = root->right;
            n->left = root;
            root->right = NULL;
            root = n;
        } else {
            root->value = value;
        }
    }
    Node *splay(Node* h, Key key){
        if (h == NULL) return NULL;
        if (key < h->key){
            if (h->left == NULL)
                return h;
            if (key < h->left->key){
                h->left->left  = splay(h->left->left, key);
                h = rotateRight(h);
            } else if (key > h->key){
                h->left->right = splay(h->left->right, key);
                if(h->left->right != NULL)
                    h->left = rotateLeft(h->left);
            }
            if (h->left == NULL) return h;
            else                 return rotateRight(h);
// rotate left done --------------
        } else if (key > h->key){
            if (h->right == NULL)
                return h;
            if (key > h->right->key){
                h->right->right  = splay(h->right->right, key);
                h = rotateLeft(h);
            } else if (key < h->key){
                h->right->left = splay(h->right->left, key);
                if(h->right->left != NULL)
                    h->right = rotateRight(h->right);
            }
            if (h->right == NULL) return h;
            else                  return rotateLeft(h);
        } else {
            return h;
        }
    }
//rotate
    Node *rotateRight(Node* h){
        Node *x  = h->left;
        h->left  = x->right;
        x->right = h;
        return x;
    }

    Node *rotateLeft (Node* h){
        Node* x  = h->right;
        h->right = x->left;
        x->left  = h;
        return x;
    }
    Value operator[] (const Key& k){
        return get(k);
    }
//debug
    void preOrder(Node *r) {
        if (r != NULL){
            printf("%d ", r->key);
            preOrder(r->left);
            preOrder(r->right);
        }
    }
    void remove(Key key){
        root = splay(root, key);
        if (k == root->key){
            if (root->left == NULL) {
                root = root->right;
            } else {
                Node x = root->right;
                root = root->left;
                root->right = x;
            }
        }
    }
    Node *low(Node *r){
        Node *tmp;
        return tmp;
    }
    Node *getMax(Node *r){
        Node *cur = r;
        while (cur->right != NULL) cur = cur->right;
        return cur;
    }
    void operator+=(SplayBST T){
        root = splay(root, getMax(root)->key);
        root->right = T.root;
    }
    SplayBST *split(Node *r){
        Node *lw = low(r);
        root = splay(root, lw->key);
        SplayBST *Tree1 = root->right;
        root->right = NULL;
        SplayBST tmp[2];
        tmp[0] = root;
        tmp[1] = Tree1;
        return tmp;
    }
};

int main(){
    SplayBST<int, string> st1;
    vector<int> arr;
    st1.put(1, "QUANG");
    st1.put(2, "TEST" );
    st1.put(3, "test2");
    st1.put(99, "LOL");
    cout << st1[99];
}