此篇仅仅作为模板使用,以 普通平衡树 为例题完成。
旋转Treap | 指针实现
#include <ctime>
#include <iostream>
#include <random>
using namespace std;
signed gen() {
static mt19937 mt(time(0));
static int cnt = 0;
cnt++;
if (cnt == 1e5) {
cnt = 0;
mt.seed(time(0));
}
return mt();
}
struct Treap {
public:
Treap() { root = NULL; }
~Treap() { clear(root); }
void insert(int val) { root = insert(root, val); }
void erase(int val) { root = erase(root, val); }
int querry_rank(int val) { return querry_rank(root, val); }
int querry_val(int rank) { return querry_val(root, rank); }
int querry_less(int val) { return querry_less(root, val); }
int querry_more(int val) { return querry_more(root, val); }
private:
struct Node {
int val, pri, cnt, size;
Node *son[2];
Node(int x) {
val = x;
cnt = 1;
size = 1;
pri = gen();
son[0] = son[1] = NULL;
}
void upd_size() {
size = cnt + count_size(son[0]) + count_size(son[1]);
}
int count_size(Node *t) {
if (t == NULL) return 0;
return t->size;
}
};
Node *root;
Node *_rotate(Node *parent, Node *son) {
auto get_d = [&]() -> int {
if (parent->son[0] == son)
return 0;
else
return 1;
};
int d = get_d(); // 0 - left, 1 - right
parent->son[d] = son->son[d ^ 1];
son->son[d ^ 1] = parent;
parent->upd_size();
son->upd_size();
return son;
}
Node *insert(Node *p, int val) {
if (p == NULL) return new Node(val);
if (p->val > val) {
p->son[0] = insert(p->son[0], val);
p->upd_size();
if (p->son[0]->pri > p->pri) p = _rotate(p, p->son[0]);
} else if (p->val < val) {
p->son[1] = insert(p->son[1], val);
p->upd_size();
if (p->son[1]->pri > p->pri) p = _rotate(p, p->son[1]);
} else {
p->cnt++;
p->upd_size();
}
return p;
}
Node *erase(Node *p, int val) {
if (p == NULL) return NULL;
if (p->val > val) {
p->son[0] = erase(p->son[0], val);
p->upd_size();
} else if (p->val < val) {
p->son[1] = erase(p->son[1], val);
p->upd_size();
} else {
if (p->cnt == 1) {
if (p->son[0] == NULL && p->son[1] == NULL) {
delete p;
return NULL;
} else if (p->son[1] == NULL) {
auto t = p->son[0];
delete p;
return t;
} else if (p->son[0] == NULL) {
auto t = p->son[1];
delete p;
return t;
} else {
if (p->son[0]->pri > p->son[1]->pri) {
p = _rotate(p, p->son[0]);
p->son[1] = erase(p->son[1], val);
} else {
p = _rotate(p, p->son[1]);
p->son[0] = erase(p->son[0], val);
}
p->upd_size();
return p;
}
} else {
p->cnt--;
p->upd_size();
}
}
return p;
}
int querry_rank(Node *p, int val) {
if (p == NULL) return 0;
if (p->val > val)
return querry_rank(p->son[0], val);
else if (p->val < val)
return p->size - p->count_size(p->son[1]) +
querry_rank(p->son[1], val);
return p->count_size(p->son[0]);
}
int querry_val(Node *p, int rank) {
if (p == NULL) return -1e9;
if (p->count_size(p->son[0]) >= rank) {
return querry_val(p->son[0], rank);
} else if (p->size - p->count_size(p->son[1]) < rank) {
return querry_val(p->son[1],
rank - p->size + p->count_size(p->son[1]));
} else {
return p->val;
}
}
int querry_less(Node *p, int val) {
if (p == NULL) return -1e9;
if (p->val >= val) return querry_less(p->son[0], val);
if (p->val < val)
return max(p->val, querry_less(p->son[1], val));
return -1e9;
}
int querry_more(Node *p, int val) {
if (p == NULL) return 1e9;
if (p->val <= val) return querry_more(p->son[1], val);
if (p->val > val)
return min(p->val, querry_more(p->son[0], val));
return 0;
}
void clear(Node *p) {
if (p == NULL) return;
clear(p->son[0]);
clear(p->son[1]);
delete p;
}
};
int main() {
cin.tie(0)->sync_with_stdio(false);
int t;
cin >> t;
Treap tp;
while (t--) {
int op, x;
cin >> op >> x;
if (op == 1) {
tp.insert(x);
} else if (op == 2) {
tp.erase(x);
} else if (op == 3) {
cout << tp.querry_rank(x) + 1 << '\n';
} else if (op == 4) {
cout << tp.querry_val(x) << '\n';
} else if (op == 5) {
cout << tp.querry_less(x) << '\n';
} else if (op == 6) {
cout << tp.querry_more(x) << '\n';
}
}
return 0;
}
有旋 Treap | 数组实现
/// @! 一定要注意,空的情况,在维护父节点的时候,必须要置空。
#include <iostream>
#include <random>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
signed gen() {
static mt19937 rng(time(0));
static int cnt = 0;
cnt++;
if (cnt == N / 10) {
cnt = 0;
rng.seed(time(0) ^ rng());
}
return rng();
}
struct Node {
int son[2], p;
int sz, cnt;
int val, pri;
void init(int v, int par) {
val = v, p = par;
sz = 1;
cnt = 1;
son[0] = son[1] = 0;
pri = gen();
}
} Tree[N];
int root = 0;
void update_size(int p) {
Tree[p].sz = Tree[p].cnt;
if (Tree[p].son[0]) Tree[p].sz += Tree[Tree[p].son[0]].sz;
if (Tree[p].son[1]) Tree[p].sz += Tree[Tree[p].son[1]].sz;
}
void _rotate(int x) {
int y = Tree[x].p;
int z = Tree[y].p;
int d = Tree[y].son[1] == x;
Tree[y].son[d] = Tree[x].son[d ^ 1];
Tree[x].son[d ^ 1] = y;
Tree[x].p = z;
Tree[y].p = x;
if (Tree[y].son[d]) Tree[Tree[y].son[d]].p = y;
update_size(y);
update_size(x);
if (z == 0)
root = x;
else
Tree[z].son[Tree[z].son[1] == y] = x;
}
int id = 0;
void insert(int v) {
// cerr << "insert " << v << endl;
int now = root, pre = 0;
while (now && Tree[now].val != v) {
pre = now;
now = Tree[pre].son[v > Tree[pre].val];
}
if (now) {
Tree[now].cnt++;
update_size(now);
} else {
now = ++id;
Tree[now].init(v, pre);
if (pre) Tree[pre].son[v > Tree[pre].val] = now;
}
while (pre && Tree[pre].pri < Tree[now].pri) {
update_size(pre);
_rotate(now);
pre = Tree[now].p;
}
while (now) {
root = now;
update_size(now);
now = Tree[now].p;
}
}
void erase(int v) {
// cerr << "IN erase " << v << endl;
int now = root, pre = 0;
while (now && Tree[now].val != v) {
pre = now;
now = Tree[pre].son[v > Tree[pre].val];
}
if (now == 0) return;
Tree[now].cnt--;
update_size(now);
if (Tree[now].cnt == 0) {
while (Tree[now].son[0] != 0 && Tree[now].son[1] != 0) {
_rotate(Tree[now].son[Tree[Tree[now].son[0]].pri <
Tree[Tree[now].son[1]].pri]);
pre = Tree[now].p;
}
if (pre) {
Tree[pre].son[Tree[pre].son[1] == now] =
Tree[now].son[0] + Tree[now].son[1];
if (Tree[now].son[0] + Tree[now].son[1])
Tree[Tree[now].son[0] + Tree[now].son[1]].p = pre;
now = pre;
} else {
root = Tree[now].son[0] + Tree[now].son[1];
if (root) Tree[root].p = 0;
now = 0;
}
}
while (now) {
root = now;
update_size(now);
now = Tree[now].p;
}
}
int querry_val(int rk) {
// cerr << "IN query_val" << endl;
int now = root;
while (rk) {
// cerr << "rk = " << rk << endl;
int Lsize = Tree[now].son[0] ? Tree[Tree[now].son[0]].sz : 0;
if (Lsize >= rk) {
now = Tree[now].son[0];
} else if (Lsize + Tree[now].cnt >= rk) {
return Tree[now].val;
} else {
rk -= Lsize + Tree[now].cnt;
now = Tree[now].son[1];
}
}
return 0;
}
int query_rank(int x) {
int now = root;
int tot = 0;
while (now && Tree[now].val != x) {
int Lsize = Tree[now].son[0] ? Tree[Tree[now].son[0]].sz : 0;
if (Tree[now].val > x) {
now = Tree[now].son[0];
} else {
tot += Lsize + Tree[now].cnt;
now = Tree[now].son[1];
}
}
if (now && Tree[now].son[0]) tot += Tree[Tree[now].son[0]].sz;
return tot + 1;
}
int nxt(int cur, int x) {
// cerr << "IN nxt " << cur << " " << x << endl;
if (cur == 0) return 1e9;
if (Tree[cur].val <= x) return nxt(Tree[cur].son[1], x);
return min(nxt(Tree[cur].son[0], x), Tree[cur].val);
}
int pre(int cur, int x) {
// cerr << "IN pre " << cur << " " << x << endl;
if (cur == 0) return -1e9;
if (Tree[cur].val >= x) return pre(Tree[cur].son[0], x);
return max(pre(Tree[cur].son[1], x), Tree[cur].val);
}
int main() {
cin.tie(0)->sync_with_stdio(false);
int t;
cin >> t;
while (t--) {
int op, x;
cin >> op >> x;
if (op == 1) insert(x);
if (op == 2) erase(x);
if (op == 3) cout << query_rank(x) << '\n';
if (op == 4) cout << querry_val(x) << '\n';
if (op == 5) cout << pre(root, x) << '\n';
if (op == 6) cout << nxt(root, x) << '\n';
}
return 0;
}
无旋 Treap | 指针实现
#include <iostream>
#include <random>
#include <tuple>
using namespace std;
unsigned gen() {
static mt19937 rng(time(nullptr));
static int cnt = 0;
cnt++;
if (cnt == 19937) {
rng.seed(time(nullptr));
cnt = 0;
}
return rng();
}
struct Treap {
struct Node {
int val, cnt, pri, size;
Node* son[2];
Node(int v) : val(v) {
pri = gen();
cnt = 1;
size = 1;
son[0] = son[1] = nullptr;
}
void upd_size() {
size = cnt;
if (son[0]) size += son[0]->size;
if (son[1]) size += son[1]->size;
}
int count_size(Node* p) {
if (p == nullptr) return 0;
return p->size;
}
};
Node* root;
Treap() : root(nullptr) {}
~Treap() { clear(root); }
tuple<Node*, Node*, Node*> split_val(Node* p, int val) {
if (p == nullptr) return {nullptr, nullptr, nullptr};
if (p->val < val) {
auto [l, m, r] = split_val(p->son[1], val);
p->son[1] = l;
p->upd_size();
return {p, m, r};
} else if (p->val == val) {
Node *l = p->son[0], *r = p->son[1];
p->son[0] = p->son[1] = nullptr;
p->upd_size();
return {l, p, r};
} else {
auto [l, m, r] = split_val(p->son[0], val);
p->son[0] = r;
p->upd_size();
return {l, m, p};
}
return {nullptr, nullptr, nullptr};
}
Node* merge(Node* l, Node* r) {
if (l == nullptr) return r;
if (r == nullptr) return l;
if (l->pri > r->pri) {
l->son[1] = merge(l->son[1], r);
l->upd_size();
return l;
} else {
r->son[0] = merge(l, r->son[0]);
r->upd_size();
return r;
}
return nullptr;
}
void insert(int v) {
auto [l, m, r] = split_val(root, v);
if (m == nullptr) {
m = new Node(v);
} else {
m->cnt++;
m->upd_size();
}
root = merge(l, merge(m, r));
}
void erase(int v) {
auto [l, m, r] = split_val(root, v);
if (m != nullptr) {
m->cnt--;
if (m->cnt == 0) {
delete m;
m = nullptr;
} else m -> upd_size();
}
root = merge(l, merge(m, r));
}
int querry_rank(int val) { return querry_rank(root, val); }
int querry_rank(Node* p, int val) {
if (p == NULL) return 0;
if (p->val > val)
return querry_rank(p->son[0], val);
else if (p->val < val)
return p->size - p->count_size(p->son[1]) +
querry_rank(p->son[1], val);
return p->count_size(p->son[0]);
}
int querry_val(int rk) { return querry_val(root, rk); }
int querry_val(Node* p, int rank) {
if (p == NULL) return -1e9;
if (p->count_size(p->son[0]) >= rank) {
return querry_val(p->son[0], rank);
} else if (p->size - p->count_size(p->son[1]) < rank) {
return querry_val(p->son[1],
rank - p->size + p->count_size(p->son[1]));
} else {
return p->val;
}
}
int querry_less(int val) { return querry_less(root, val); }
int querry_less(Node* p, int val) {
if (p == NULL) return -1e9;
if (p->val >= val) return querry_less(p->son[0], val);
if (p->val < val)
return max(p->val, querry_less(p->son[1], val));
return -1e9;
}
int querry_more(int val) { return querry_more(root, val); }
int querry_more(Node* p, int val) {
if (p == NULL) return 1e9;
if (p->val <= val) return querry_more(p->son[1], val);
if (p->val > val)
return min(p->val, querry_more(p->son[0], val));
return 0;
}
void clear(Node* p) {
if (p == NULL) return;
clear(p->son[0]);
clear(p->son[1]);
delete p;
}
};
int main() {
cin.tie(0)->sync_with_stdio(false);
int t;
cin >> t;
Treap tp;
while (t--) {
int op, x;
cin >> op >> x;
if (op == 1) {
tp.insert(x);
} else if (op == 2) {
tp.erase(x);
} else if (op == 3) {
cout << tp.querry_rank(x) + 1 << '\n';
} else if (op == 4) {
cout << tp.querry_val(x) << '\n';
} else if (op == 5) {
cout << tp.querry_less(x) << '\n';
} else if (op == 6) {
cout << tp.querry_more(x) << '\n';
}
}
return 0;
}
无旋 Treap | 数组模拟
#include <iostream>
#include <random>
#include <tuple>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
signed gen() {
static mt19937 rng(time(0));
static int cnt = 0;
cnt++;
if (cnt == N / 10) {
cnt = 0;
rng.seed(time(0) ^ rng());
}
return rng();
}
struct Node {
int son[2];
int sz, cnt;
int val, pri;
void init(int v) {
val = v;
sz = 1;
cnt = 1;
son[0] = son[1] = 0;
pri = gen();
}
} Tree[N];
int root = 0;
// FHQ-Treap
void update_size(int p) {
Tree[p].sz = Tree[p].cnt;
if (Tree[p].son[0]) Tree[p].sz += Tree[Tree[p].son[0]].sz;
if (Tree[p].son[1]) Tree[p].sz += Tree[Tree[p].son[1]].sz;
}
int id = 0;
pair<int, int> split(int cur, int v) {
// 分裂成 [-inf , v] 和 [v + 1 , inf]
if (cur == 0) return {0, 0};
if (Tree[cur].val > v) {
auto [l, r] = split(Tree[cur].son[0], v);
Tree[cur].son[0] = r;
update_size(cur);
return {l, cur};
} else {
auto [l, r] = split(Tree[cur].son[1], v);
Tree[cur].son[1] = l;
update_size(cur);
return {cur, r};
}
return {0, 0};
}
int merge(int l, int r) {
// 合并两个子树
if (l == 0 || r == 0) return l + r;
if (Tree[l].pri > Tree[r].pri) {
Tree[l].son[1] = merge(Tree[l].son[1], r);
update_size(l);
return l;
} else {
Tree[r].son[0] = merge(l, Tree[r].son[0]);
update_size(r);
return r;
}
return 0;
}
void insert(int v) {
auto [t, r] = split(root, v); // [-inf , v] , [v + 1 , inf]
auto [l, m] = split(t, v - 1);// [-inf , v - 1] , [v , v]
if (m == 0) {
m = ++id;
Tree[m].init(v);
} else {
Tree[m].cnt++;
Tree[m].sz++;
}
root = merge(merge(l, m), r);
}
void erase(int v) {
auto [t, r] = split(root, v); // [-inf , v] , [v + 1 , inf]
auto [l, m] = split(t, v - 1);// [-inf , v - 1] , [v , v]
if (m != 0) {
Tree[m].cnt--;
Tree[m].sz--;
if (Tree[m].cnt == 0) m = 0;
}
root = merge(l, merge(m, r));
}
int querry_val(int rk) {
int now = root;
while (rk) {
int Lsize = Tree[now].son[0] ? Tree[Tree[now].son[0]].sz : 0;
if (Lsize >= rk) {
now = Tree[now].son[0];
} else if (Lsize + Tree[now].cnt >= rk) {
return Tree[now].val;
} else {
rk -= Lsize + Tree[now].cnt;
now = Tree[now].son[1];
}
}
return 0;
}
int query_rank(int x) {
int now = root;
int tot = 0;
while (now && Tree[now].val != x) {
int Lsize = Tree[now].son[0] ? Tree[Tree[now].son[0]].sz : 0;
if (Tree[now].val > x) {
now = Tree[now].son[0];
} else {
tot += Lsize + Tree[now].cnt;
now = Tree[now].son[1];
}
}
if (now && Tree[now].son[0]) tot += Tree[Tree[now].son[0]].sz;
return tot + 1;
}
int nxt(int cur, int x) {
if (cur == 0) return 1e9;
if (Tree[cur].val <= x) return nxt(Tree[cur].son[1], x);
return min(nxt(Tree[cur].son[0], x), Tree[cur].val);
}
int pre(int cur, int x) {
if (cur == 0) return -1e9;
if (Tree[cur].val >= x) return pre(Tree[cur].son[0], x);
return max(pre(Tree[cur].son[1], x), Tree[cur].val);
}
int main() {
cin.tie(0)->sync_with_stdio(false);
int t;
cin >> t;
while (t--) {
int op, x;
cin >> op >> x;
if (op == 1) insert(x);
if (op == 2) erase(x);
if (op == 3) cout << query_rank(x) << '\n';
if (op == 4) cout << querry_val(x) << '\n';
if (op == 5) cout << pre(root, x) << '\n';
if (op == 6) cout << nxt(root, x) << '\n';
}
return 0;
}
无旋 Treap 实现区间操作 | 指针实现
#include <iostream>
#include <random>
#include <tuple>
using namespace std;
unsigned gen() {
static mt19937 rng(time(nullptr));
static int cnt = 0;
cnt++;
if (cnt == 100000) {
rng.seed(time(nullptr));
cnt = 0;
}
return rng();
}
struct Treap {
struct Node {
int val, pri, size, cnt;
Node* son[2];
int lz;
Node(int v) : val(v) {
size = 1;
cnt = 1;
pri = gen();
son[0] = son[1] = nullptr;
lz = 0;
};
void upd_size() {
size = cnt;
if (son[0]) size += son[0]->size;
if (son[1]) size += son[1]->size;
}
void push_down() {
if (lz) {
swap(son[0], son[1]);
if (son[0]) son[0]->lz ^= lz;
if (son[1]) son[1]->lz ^= lz;
lz = 0;
}
}
};
Node* root;
Treap() : root(nullptr) {}
pair<Node*, Node*> split_size(Node* p, int sz) {
if (p == nullptr) return {nullptr, nullptr};
p->push_down();
int l_size = p->son[0] ? p->son[0]->size : 0;
if (l_size >= sz) {
auto [l, r] = split_size(p->son[0], sz);
p->son[0] = r;
p->upd_size();
return {l, p};
} else {
auto [l, r] = split_size(p->son[1], sz - l_size - 1);
p->son[1] = l;
p->upd_size();
return {p, r};
}
return {nullptr, nullptr};
}
Node* merge(Node* l, Node* r) {
if (l == nullptr && r == nullptr) return nullptr;
if (l == nullptr) return r;
if (r == nullptr) return l;
l->push_down(), r->push_down();
if (l->pri > r->pri) {
l->son[1] = merge(l->son[1], r);
l->upd_size();
return l;
} else {
r->son[0] = merge(l, r->son[0]);
r->upd_size();
return r;
}
return nullptr;
}
void insert(int v) {
auto [l, t] = split_size(root, v);
auto [m, r] = split_size(t, v + 1);
if (m == nullptr)
m = new Node(v);
else
m->cnt++, m->upd_size();
root = merge(merge(l, m), r);
}
void erase(int v) {
auto [l, t] = split_size(root, v);
auto [m, r] = split_size(t, v + 1);
if (m != nullptr) {
m->cnt--;
if (m->cnt == 0) delete m, m = nullptr;
else m -> upd_size();
}
root = merge(merge(l, m), r);
}
void reverse(int lv, int rv) {
auto [l, t] = split_size(root, lv - 1);
auto [m, r] = split_size(t, rv - lv + 1);
if (m != nullptr) m->lz ^= 1;
root = merge(merge(l, m), r);
}
void print(Node* p) {
if (p == nullptr) return;
p->push_down();
print(p->son[0]);
cout << p->val << " ";
print(p->son[1]);
}
void print() { print(root); }
};
int main() {
int n, m;
cin >> n >> m;
Treap tp;
for (int i = 1; i <= n; i++) tp.insert(i);
while (m--) {
int l, r;
cin >> l >> r;
tp.reverse(l, r);
// for (int i = 1; i <= n; i++) cout << i << ' ';
// cout << '\n';
// for (int i = 1; i <= n; i++) cout << '|' << ' ';
// cout << '\n';
// for (int i = 1; i <= n; i++) cout << 'v' << ' ';
// cout << '\n';
// tp.print();
// cout << '\n';
// cout << '\n';
}
tp.print();
return 0;
}
PREVIOUS2022 牛客多校第二场题解(D)
NEXT2022 牛客多校第四场题解