POJ 1442 Black Box - (无旋Treap)

题目链接：http://poj.org/problem?id=1442
无旋treap挺好用，参考：https://www.bilibili.com/video/av46204315/?p=2

#include <iostream>
#include <queue>
#include <stdlib.h>
#include <cstdio>using namespace std;#define maxn (30000 + 5)inline int read_int() {
     int a; scanf("%d", &a); return a; }
inline void outd(int x) {
     printf("%d", x); }
inline void outdn(int x) {
     printf("%d\n", x); }
inline void outn() {
     printf("\n"); }// refers to "https://www.bilibili.com/video/av46204315/?p=2"
struct treap_node {
    intleft,  // 左子树right, // 右子树bst_v, // BST值pri_v, // 最小堆值（随机生成）size;  // 树大小，包括自己
};
treap_node treap[maxn]; // 0 是不用的
int root = 0;
int cur_no = 0;
int total_size = 0;#define lc(root) treap[root].left
#define rc(root) treap[root].right
inline void update_size(int root) {
     treap[root].size = treap[lc(root)].size + treap[rc(root)].size + 1; }// 将 root 划分为 left 和 right 两棵 treap
// 按照 bst_v 来分 BST，结果得到 left树 BST <= right树
void split(int root, int& left, int& right, int bst_v) {
    // 空树if (root == 0) {
    left = right = 0;return;}// root 和 其左子树应该划分给 left，// 剩下的右子树 再 split 分给 left右子树（左边的一部分） 和 right// 相当于 "不断地裁掉一节，然后接到左右treap上"if (treap[root].bst_v <= bst_v) {
    left = root;split(rc(root), rc(left), right, bst_v);}else {
    right = root;split(lc(root), left, lc(right), bst_v);}update_size(root);
}// 按照最小堆 merge，把 left树 和 right树 merge 的结果写到 root
// 调用者保证 left树 BST <= right树
void merge(int& root, int left, int right) {
    // 空树if (left == 0 || right == 0) {
    root = left | right;return;}// 让 left 成为 root，并且连带其左子树（BST性质）// 然后 其右子树 和 right树 再次合并为 left 的右子树if (treap[left].pri_v < treap[right].pri_v) {
    root = left;merge(rc(root), rc(left), right);}else {
    root = right;merge(lc(root), left, lc(right));}update_size(root);
}void insert(int& root, int bst_v) {
    total_size++;cur_no++;treap[cur_no].size = 1;treap[cur_no].bst_v = bst_v;treap[cur_no].pri_v = rand();int left, right;split(root, left, right, bst_v); // left树 <= bst_v，right树 > bst_vmerge(left, left, cur_no);   	 // 保证 left树 <= right树，把新值加进去merge(root, left, right);        // 再合起来
}void erase(int& root, int bst_v) {
    int left, right, victim;split(root, left, right, bst_v);split(left, left, victim, bst_v - 1); 	// victim树 里面都是 bst_vif (treap[victim].size > 0)total_size--;merge(victim, lc(victim), lc(victim)); 	// 去掉根这个值merge(left, left, victim);merge(root, left, right);
}// 区间第K大
// 寻找中序遍历第K个
int Kth_element(int root, int K) {
    while (treap[lc(root)].size != K - 1) {
    if (treap[lc(root)].size >= K)root = lc(root);else {
    K -= treap[lc(root)].size + 1;root = rc(root);}}return treap[root].bst_v;
}// 查询 bst_v 的排名
int get_rank(int& root, int bst_v) {
    int left, right;split(root, left, right, bst_v - 1); // left树 <= bst_vint answer = treap[left].size + 1;merge(root, left, right);return answer;
}// 前驱，即满足 "小于bst_v" 的最大的数
int precursor(int& root, int bst_v) {
    int left, right;split(root, left, right, bst_v - 1); // left树 <= bst_vint answer = Kth_element(left, treap[left].size); // left树中的最大值merge(root, left, right);return answer;
}// 后继，即满足 "大于bst_v" 的最小的数
int successor(int& root, int bst_v) {
    int left, right;split(root, left, right, bst_v); // right树 > bst_vint answer = Kth_element(right, 1); // right树中的最小值merge(root, left, right);return answer;
}int main() {
    srand(19971206);int M, N, i = 0;queue<int> add, get;M = read_int();N = read_int();int temp;for (int i = 0; i < M; i++)add.push(read_int());for (int i = 0; i < N; i++)get.push(read_int());i = 0;while (!get.empty()){
    const int size = get.front();while (total_size < size){
    insert(root, add.front());add.pop();}outdn(Kth_element(root, ++i));get.pop();}system("pause");return 0;
}