来一篇指针版无旋Treap

题目大意

维护一组数据,支持插入和查找中位数,如果数据个数为偶数那么选较小的一个

前置知识

$FHQTreap$,可以看我博客

思路

在对树进行$Split$的时候按照$size$分裂而不是权值,插入操作时查一下$rank$,拆开树再夹进去。查中位数时候拆出$size$为$\frac{root->size-1}{2}$的左树,然后在右树中拆出一个节点即为中位数

代码

#include <stdio.h>

int Rand() {
    static int seed = 123456;
    return seed = (((seed ^ 666666) + 19260817ll) * 1433223ll) % 0x3f3f3f3f;
}

namespace FHQ{
    struct Node{
        int val, key, size;
        Node *child[2];
        Node(int val):val(val), key(Rand()), size(1){child[0] = child[1] = NULL;}
    };

    Node *root = NULL;

    void Update(Node *now) {
        now->size = 1;
        now->size += now->child[0] ? now->child[0]->size : 0;
        now->size += now->child[1] ? now->child[1]->size : 0;
    }


    void Split(Node *now, int k, Node *&t1, Node *&t2) {
        if (!now) {
            t1 = t2 = NULL; return;
        }
        if (k == 0) {
            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 (k <= ls) {
            Node *temp;
            Split(now->child[0], k, t1, temp); 
            t2 = now; t2->child[0] = temp; Update(t2); return;
        } else {
            Node *temp;
            Split(now->child[1], k - ls - 1, temp, t2);
            t1 = now; t1->child[1] = temp; Update(t1); return;
        }
    }

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

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

    void Insert(int k) {
        if (!root) {
            root = new Node(k);
            return;
        }
        int rank = Rank(root, k);
        Node *lt, *rt;
        Split(root, rank - 1, lt, rt);
        root = Merge(lt, Merge(new Node(k), rt));
    }

    int GetMid() {
        Node *lt, *rt, *temp, *node;
        Split(root, root->size - 1 >> 1, lt, temp);
        Split(temp, 1, node, rt);
        int res = node->val;
        root = Merge(lt, Merge(node, rt));
        return res;
    }
}

int n, m, x;
char str[5];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &x);
        FHQ::Insert(x);
    }
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        scanf("%s", str);
        if (str[0] == 'a') {
            scanf("%d", &x);
            FHQ::Insert(x);
        } else {
            printf("%d\n", FHQ::GetMid());
        }
    }
    return 0;
}
/*
6
1 2 13 14 15 16
5
add 5
add 3
mid
add 20
mid
*/

话说一楼的zip-tree看起来比fhq还要好写,要学一波了