POJ1442黑箱问题（使用Treap解决）

题目链接：POJ 1442。

题目描述：本题涉及一系列操作，包括向数据结构中插入数值和从数据结构中获取数值。获取的数值是当前数据集中第K大的数，且每次获取后K值自动增加1。

解决方案：虽然此问题可以通过多种数据结构来解决，但这里选择使用Treap（一种随机化二叉搜索树）来实现。Treap结合了二叉搜索树和堆的特点，既保持了元素的有序性，又通过随机优先级确保了树的高度接近对数级别，从而保证了高效的操作性能。

#include 
#include 
using namespace std;

vector values;

struct TreapNode {
    TreapNode *left, *right;
    int value, priority;
    TreapNode(int val) : value(val), priority(rand()), left(NULL), right(NULL) {}
};

TreapNode* root = NULL;

void rotateLeft(TreapNode*& node) {
    TreapNode* temp = node->right;
    node->right = temp->left;
    temp->left = node;
    node = temp;
}

void rotateRight(TreapNode*& node) {
    TreapNode* temp = node->left;
    node->left = temp->right;
    temp->right = node;
    node = temp;
}

void inOrderTraversal(TreapNode* node) {
    if (node != NULL) {
        inOrderTraversal(node->left);
        values.push_back(node->value);
        inOrderTraversal(node->right);
    }
}

void insert(TreapNode*& node, int value) {
    if (node == NULL) {
        node = new TreapNode(value);
    } else if (value <= node->value) {
        insert(node->left, value);
        if (node->left->priority priority) rotateRight(node);
    } else {
        insert(node->right, value);
        if (node->right->priority priority) rotateLeft(node);
    }
}

int main() {
    int n, m, k = 1;
    cin >> n >> m;
    vector inputs(n + 1), queries(m + 1);
    for (int i = 1; i <= n; ++i) cin >> inputs[i];
    for (int i = 1; i <= m; ++i) {
        int x;
        cin >> x;
        queries[x]++;
    }
    for (int i = 1; i <= n; ++i) {
        insert(root, inputs[i]);
        if (queries[i]) {
            values.clear();
            inOrderTraversal(root);
            for (int j = 0; j                 cout <                k++;
            }
        }
    }
    return 0;
}

参考来源：NightRaven的博客