Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdint>
- #include <cstdio>
- #include <initializer_list>
- // Xoshiro256** 32bit
- static uint64_t rotl(const uint64_t x, int k) {
- return (x << k) | (x >> (64 - k));
- }
- static uint32_t rng() {
- static uint64_t s[4] = {123456789, 987654321, 999778844, 99999999};
- const uint64_t ret = rotl(s[1] * 5, 7) * 9;
- const uint64_t t = s[1] << 17;
- s[2] ^= s[0]; s[3] ^= s[1]; s[1] ^= s[2]; s[0] ^= s[3];
- s[2] ^= t; s[3] = rotl(s[3], 45);
- return ret >> 32;
- }
- // Treap
- struct node {
- node *l, *r;
- int val;
- uint32_t t;
- node() = default;
- node(int v) : val(v) {
- l = r = nullptr;
- t = rng();
- }
- ~node() {
- delete l;
- delete r;
- }
- };
- typedef node *pnode;
- pnode treap_merge(pnode left, pnode right) {
- if (!left) return right;
- if (!right) return left;
- if (left->t > right->t) {
- left->r = treap_merge(left->r, right);
- return left;
- }
- right->l = treap_merge(left, right->l);
- return right;
- }
- void treap_split(pnode root, int k, pnode &left, pnode &right) {
- if (!root) {
- left = nullptr;
- right = nullptr;
- } else if (root->val < k) {
- treap_split(root->r, k, root->r, right);
- left = root;
- } else {
- treap_split(root->l, k, left, root->l);
- right = root;
- }
- }
- void printAll(pnode a) {
- if (!a) return;
- printAll(a->l);
- printf("%d ", a->val);
- printAll(a->r);
- }
- class Treap {
- pnode root = nullptr;
- public:
- void insert(int p) {
- pnode left, right;
- treap_split(root, p, left, right);
- root = treap_merge(treap_merge(left, new node(p)), right);
- }
- void remove(int p) {
- pnode left, mid, right;
- treap_split(root, p, left, mid);
- treap_split(mid, p + 1, mid, right);
- root = treap_merge(left, right);
- delete mid;
- }
- void print() {
- printf("[ ");
- printAll(root);
- printf("]");
- }
- };
- int main() {
- Treap tr;
- for (const auto& x : {1, 9, 3, 4, 7, 6, 8, 2}) tr.insert(x);
- for (const auto& x : {7, 3}) tr.remove(x);
- tr.print(); // [ 1 2 4 6 8 9 ]
- }
Add Comment
Please, Sign In to add comment