我看这么多题解没有人写指针版的无旋Treap,我来写一个

如果不会FHQTreap可以看我的博客

指针版FHQ又好写又好调跑的还快,墙裂推荐

题面无需多讲,插入数值和查询第$k$小,平衡树模板操作

无旋$Treap$由于有按照$size$来$Split$的功能,所以我们可以按照二叉搜索树的性质写一个$Rank$函数,然后这两种操作都可以基于$Rank$完成

插入数值

查$Rank$,分裂出$size$为$Rank - 1$的子树,把新节点放入中间合并,代码如下

void Insert(int val) {
    int rank = Rank(root, val);
    Node *temp1, *temp2;
    Split(root, rank, temp1, temp2);
    Node *nod = new Node(val);
    root = Merge(temp1, nod);
    root = Merge(root, temp2);
}

查询第k小

按照需要的$k$值分裂出$size$为$k - 1$的子树,在剩余部分分裂出$size$为$1$的节点,输出节点权值,然后原样拼回去,代码如下

int FindKth(int k) {
    Node *x1, *x2, *y1, *y2;
    Split(root, k - 1, x1, x2);
    Split(x2, 1, y1, y2);
    Node *now = y1;
    root = Merge(x1, Merge(now, y2));
    return now ? now->val : 0;
}

完整代码

#include <cstdio>
#include <algorithm>

using std::min;
using std::max;

const int MAXM = 2e5 + 5;

int add[MAXM], get[MAXM];

int n, m;

int Rand() {
    static int seed = 39444;
    return seed = (((seed ^ 1433223) + 810872ll) * 19260817ll) % 2147483647;
}

struct Node{
    Node *child[2];
    int val, key, size;
    
    Node(int val):val(val), size(1), key(Rand()) {
        child[0] = NULL; child[1] = NULL;
    }
    
    void Update() {
        size = 1;
        if (child[0]) size += child[0]->size;
        if (child[1]) size += child[1]->size;
    }
};

Node *root = NULL;

Node* Merge(Node* a, Node* b) {
    if (!a || !b) return a ? a : b;
    if (a->key < b->key) {
        a->child[1] = Merge(a->child[1], b);
        a->Update();
        return a;
    } else {
        b->child[0] = Merge(a, b->child[0]);
        b->Update();
        return b;
    }
}

void Split(Node *now, int k, Node *&t1, Node *&t2) {
    if (!now) {
        t1 = t2 = NULL; return;
    } 
    if (!k) {
        t1 = NULL; t2 = now; return;
    }
    if (k >= now->size) {
        t1 = now; t2 = NULL; return;
    }
    int ls = now->child[0] ? now->child[0]->size : 0;
    if (ls >= k) {
        Node *temp;
        Split(now->child[0], k, t1, temp);
        t2 = now; t2->child[0] = temp; 
        t2->Update(); return;
    } else {
        Node *temp;
        Split(now->child[1], k - ls - 1, temp, t2);
        t1 = now; t1->child[1] = temp;
        t1->Update(); return;
    }
}

int Rank(Node *now, int k) {
    if (!now) return 0;
    int ls = now->child[0] ? now->child[0]->size : 0;
    if (now->val <= k) return ls + 1 + Rank(now->child[1], k);
    else return Rank(now->child[0], k);
}

int FindKth(int k) {
    Node *x1, *x2, *y1, *y2;
    Split(root, k - 1, x1, x2);
    Split(x2, 1, y1, y2);
    Node *now = y1;
    root = Merge(x1, Merge(now, y2));
    return now ? now->val : 0;
}

void Insert(int val) {
    int rank = Rank(root, val);
    Node *temp1, *temp2;
    Split(root, rank, temp1, temp2);
    Node *nod = new Node(val);
    root = Merge(temp1, nod);
    root = Merge(root, temp2);
}

int main() {
    scanf("%d %d", &m, &n);
    for (int i = 1; i <= m; i++) {
        scanf("%d", add + i);
    }
    int ii = 0, cur = 1;
    for (int i = 1; i <= n; i++) {
        scanf("%d", get + i);
        while (cur <= get[i]) {
            Insert(add[cur]); cur++;
        }
        printf("%d\n", FindKth(++ii));
    }
    return 0;
}