codes/persistent_cartesian.hpp at master · notimesea/codes · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
using ll = long long;

// Base used for polynomial hashing inside the treap
const ll Q = 239017;

struct hdata {
    ll h1;
    ll h2;
    ll h3;

    hdata() {
        h1 = 0;
        h2 = 0;
        h3 = 1;
    }

    hdata operator+(const hdata &r) const {
        hdata res;
        res.h1 = h1 * r.h3 + r.h1;
        res.h2 = r.h2 * h3 + h2;
        res.h3 = h3 * r.h3;
        return res;
    }

    hdata(int key) {
        h1 = key;
        h2 = key;
        h3 = Q;
    }
};

struct item;

typedef shared_ptr<item> pitem;

hdata geth(pitem t);

int getq(pitem t);

struct item {
    int q;
    int value;
    hdata hash;
    pitem l, r;
    char rev;

    item() {}

    item(int value, pitem l = nullptr, pitem r = nullptr) : value(value), l(l), r(r) {
        q = 1 + getq(l) + getq(r);
        hash = geth(l) + value + geth(r);
        rev = 0;
    }
    item(pitem x) : q(x->q), value(x->value), hash(x->hash), l(x->l), r(x->r), rev(1) {
        swap(hash.h1, hash.h2);
    }
};

hdata empty_h;

hdata geth(pitem t) {
    if (t != nullptr) return t->hash;
    else return empty_h;
}

int getq(pitem t) {
    if (t != nullptr) return t->q;
    else return 0;
}

pitem rev(pitem v) {
    if (v == nullptr) return nullptr;
    return make_shared<item>(v);
}

pitem push(pitem v) {
    if (v == nullptr) return nullptr;
    if (!v->rev) return v;
    return make_shared<item>(v->value, rev(v->r), rev(v->l));
}

mt19937 gen;

bool random(int a, int b) {
    return gen() % (a + b) < a;
}

inline pitem merge(pitem l, pitem r) {
    if (l == nullptr || r == nullptr)
        return l != nullptr ? l : r;
    else if (random(l->q, r->q)) {
        l = push(l);
        return make_shared<item>(l->value, l->l, merge(l->r, r));
    } else {
        r = push(r);
        return make_shared<item>(r->value, merge(l, r->l), r->r);
    }
}

inline pair<pitem, pitem> split(pitem root, int cnt) {
    if (root == nullptr)
        return make_pair(nullptr, nullptr);
    root = push(root);
    if (cnt <= getq(root->l)) {
        pair<pitem, pitem> splitted = split(root->l, cnt);
        return make_pair(splitted.first, make_shared<item>(root->value, splitted.second, root->r));
    } else {
        pair<pitem, pitem> splitted = split(root->r, cnt - getq(root->l) - 1);
        return make_pair(make_shared<item>(root->value, root->l, splitted.first), splitted.second);
    }
}

void print(pitem p, int d = 0) {
    if (p == nullptr) {
        return;
    }
    p = push(p);
    print(p->l, d + 1);
    cout << p->value << " ";
    print(p->r, d + 1);
}

pitem reverse(pitem root, int l, int r) {
    auto t1 = split(root, l);
    auto t2 = split(t1.y, r - l);
    t2.x = rev(t2.x);
    return merge(t1.x, merge(t2.x, t2.y));
}