Cartesion Tree

gistfile1.cpp

#include <bits/stdc++.h>

using namespace std;

struct Node {
    int key;
    double prior;
    int height;
    Node* left;
    Node* right;


    Node(int key) : key(key), prior(rand()*1.0/INT_MAX), height(1) {}
};

typedef Node* PNode;

int height(PNode node) {
    return node ? node->height : 0;
}

void recalcHeight(PNode node) {
    if(node != nullptr) {
        node->height = height(node->left) + height(node->right) + 1;
    }
}

PNode merge(PNode left, PNode right) {
    if(left == nullptr)
        return right;

    if(right == nullptr)
        return left;

    if(left->prior > right->prior) {
        left->right = merge(left->right, right);
        recalcHeight(left);
        return left;
    } else {
        right->left = merge(left, right->left);
        recalcHeight(right);
        return right;
    }
}

void split(PNode root, PNode& left, PNode& right, int key) {
    if(root == nullptr) {
        left = right = nullptr;
    } else if(key < root->key) {
        split(root->left, left, root->left, key);
        right = root;
        recalcHeight(right);
    } else {
        split(root->right, root->right, right, key);
        left = root;
        recalcHeight(left);
    }
}

PNode find(PNode root, int key) {
    if(root == nullptr || root->key == key)
        return root;

    if(key < root->key)
        return find(root->left, key);

    return find(root->right, key);
}

void add(PNode& root, int key) {
    if(find(root, key) == nullptr) {
        PNode left;
        PNode right;
        split(root, left, right, key);
        root = merge(merge(left, new Node(key)), right);
    }
}

void remove(PNode& root, int key) {
    if(find(root, key) != nullptr) {
        PNode left;
        PNode right;
        split(root, left, right, key - 1);

        PNode left2;
        PNode right2;
        split(right, left2, right2, key + 1);

        root = merge(left, right2);
    }
}

PNode get_kth(PNode root, int k) {
    if(height(root->right) == k)
        return root;

    if(height(root->right) > k )
        return get_kth(root->right, k);

    return get_kth(root->left, k - height(root->right) - 1);
}

int main(void) {
    srand(time(0));

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

    PNode root = nullptr;
    for(int i = 0; i < n; i++) {
        int cmd, value;
        scanf("%d%d", &cmd, &value);

        if(cmd == 1) {
            add(root, value);
        } else if(cmd == 0) {
            printf("%d\n", get_kth(root, value - 1)->key);
        } else {
            remove(root, value);
        }
    }

    return 0;
}