Policy-Based Data Structures (PBDS) trong C++
Thư viện pb_ds của GCC: ordered_set với find_by_order và order_of_key, multiset bằng cặp (giá trị, id), gp_hash_table chống hack, priority_queue có join và modify, rope; kèm phương án thay thế trong Python.
Policy-Based Data Structures (PBDS, thư viện pb_ds của GCC) là bộ cấu trúc dữ liệu "có sẵn" đi kèm trình biên dịch GCC, không thuộc chuẩn C++ nhưng dùng được trên hầu hết các judge. Món quý nhất là cây thống kê thứ tự (order statistics tree): một std::set biết thêm hai phép tìm phần tử nhỏ thứ và đếm số phần tử nhỏ hơn , cả hai trong , trong khi std::set phải duyệt tuần tự mất . Ngoài ra pb_ds còn có bảng băm gp_hash_table nhanh hơn unordered_map, hàng đợi ưu tiên hỗ trợ gộp (join) và sửa khoá (modify), và rope cho phép cắt dán đoạn của dãy trong . Trang này là bản tra cứu nhanh kèm các bẫy thường gặp; phần STL chuẩn xem ở C++ STL Cheatsheet.
Ý tưởng / Trực giác
Vì sao std::set không trả lời được "phần tử thứ "?
std::set là cây đỏ đen: mỗi nút chỉ biết khoá của mình và hai con. Muốn biết "khoá đứng thứ mấy", cây phải đếm số nút bên trái , và không có thông tin nào giúp đếm nhanh, nên distance(s.begin(), it) tốn .
Cách sửa rất tự nhiên: mỗi nút lưu thêm kích thước cây con của nó. Khi đó tại một nút có cây con trái kích thước :
- nếu : phần tử thứ (đếm từ ) nằm trong cây con trái, đi xuống trái;
- nếu : chính là ;
- nếu : đi xuống phải với .
Mỗi bước xuống một tầng, cây đỏ đen cao , nên tìm phần tử thứ tốn . Đếm số phần tử nhỏ hơn làm ngược lại: đi từ gốc tìm , mỗi lần rẽ phải thì cộng kích thước cây con trái cộng . Kích thước cây con chỉ thay đổi trên đường từ nút bị chèn/xoá lên gốc và ở các nút bị xoay, nên vẫn cập nhật được trong .
pb_ds cài sẵn đúng ý tưởng này dưới tên chính sách cập nhật nút tree_order_statistics_node_update. Chữ "policy-based" nghĩa là: ta ghép cấu trúc từ các "chính sách" (kiểu cây, hàm so sánh, dữ liệu phụ lưu ở nút) thay vì viết lại từ đầu. Đây cũng chính là "cây BST có lưu size" trong Treap, chỉ khác là GCC cài hộ ta.
Ba công cụ còn lại
gp_hash_table: bảng băm địa chỉ mở (open addressing), dò tuyến tính trên mảng liên tục nên ít cấp phát bộ nhớ và thân thiện cache hơnunordered_map(mỗi phần tử là một nút danh sách liên kết riêng). Thường nhanh hơn khoảng đến lần. Lý thuyết bảng băm xem Bảng băm.__gnu_pbds::priority_queue: mặc định là pairing heap. Khácstd::priority_queue, nó trả về một "tay cầm" (point_iterator) cho mỗi phần tử, nhờ đó ta sửa khoá hoặc xoá một phần tử bất kỳ, và gộp hai heap trong .__gnu_cxx::rope: dãy biểu diễn bằng cây, chèn/xoá/cắt một đoạn ở giữa dãy trong thay vì nhưvector.
Ví dụ chạy tay
Cây thống kê thứ tự: find_by_order và order_of_key
Chèn lần lượt vào ordered_set. Tập luôn được giữ có thứ tự, ta hình dung nó như một mảng đã sắp xếp đánh số từ :
array base=0 1 3 5 8 9 step find_by_order(2): phần tử ở vị trí 2 (nhỏ thứ ba) là 5 highlight green 2 step order_of_key(6): các phần tử nhỏ hơn 6 là 1, 3, 5, trả về 3 clear highlight orange 0..2 step order_of_key(5): chỉ đếm phần tử NHỎ HƠN HẲN 5, trả về 2 clear highlight orange 0..1 highlight red 2
| Lệnh | Kết quả | Giải thích |
|---|---|---|
*s.find_by_order(0) |
1 |
phần tử nhỏ nhất |
*s.find_by_order(2) |
5 |
nhỏ thứ ba (đếm từ ) |
s.find_by_order(5) == s.end() |
true |
size trả về end() |
s.order_of_key(6) |
3 |
số phần tử |
s.order_of_key(5) |
2 |
so sánh ngặt, không được đếm |
s.erase(3) rồi *s.find_by_order(1) |
5 |
tập còn |
Multiset bằng cặp (giá trị, chỉ số)
ordered_set không chứa được hai phần tử bằng nhau. Mẹo chuẩn: lưu cặp với là số thứ tự chèn, khác nhau cho mọi lần chèn. Các cặp không bao giờ trùng, và sắp theo cặp thì vẫn sắp theo trước. Xét chuỗi thao tác:
+ 5 + 2 + 5 + 8 ? 3 # 5 - 5 ? 3 ? 4
(+ x: chèn, - x: xoá một bản sao, ? k: phần tử nhỏ thứ đếm từ , # x: số phần tử .)
array base=0 (2,1) (5,0) (5,2) (8,3) step Sau 4 lần chèn: id lần lượt là 0, 1, 2, 3 step ? 3: find_by_order(2) là cặp (5,2), in 5 highlight green 2 step # 5: order_of_key((5, INT_MIN)) đếm các cặp nhỏ hơn (5, -vô cùng), chỉ có (2,1), in 1 clear highlight orange 0 step - 5: lower_bound((5, INT_MIN)) trỏ tới (5,0), xoá đúng một bản sao clear highlight red 1
Sau khi xoá, tập là : ? 3 in , ? 4 in (không tồn tại). Toàn bộ output là 5 1 8 -1, khớp với chương trình ở phần Cài đặt.
Điểm mấu chốt: muốn "đếm số phần tử " thì truy vấn order_of_key({x, INT_MIN}); muốn "đếm số phần tử " thì order_of_key({x, INT_MAX}).
Đếm nghịch thế online
Dãy . Duyệt từ trái sang phải; trước khi chèn , số phần tử đã gặp lớn hơn bằng :
array
4 2 4 1 3
step j=1, a=4: chưa có gì, cộng 0
highlight blue 1
step j=2, a=2: đã có {4}, số phần tử lớn hơn 2 là 1
highlight orange 1
highlight blue 2
step j=3, a=4: đã có {2, 4}, phần tử bằng 4 KHÔNG tính, cộng 0
clear
highlight blue 3
step j=4, a=1: đã có {2, 4, 4}, cả 3 đều lớn hơn 1, cộng 3
clear
highlight orange 1..3
highlight blue 4
step j=5, a=3: đã có {1, 2, 4, 4}, hai số 4 lớn hơn 3, cộng 2
clear
highlight orange 1 3
highlight blue 5
| đã gặp (đã sắp) | số phần tử | cộng thêm | ||
|---|---|---|---|---|
| 1 | 4 | 0 | 0 | |
| 2 | 2 | 0 | 1 | |
| 3 | 4 | 2 | 0 | |
| 4 | 1 | 0 | 3 | |
| 5 | 3 | 2 | 2 |
Tổng: nghịch thế: .
Cài đặt
Khai báo ordered_set và ordered_map
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
// ordered_set: like std::set, plus find_by_order and order_of_key
template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,
tree_order_statistics_node_update>;
// ordered_map: like std::map; find_by_order returns an iterator to (key, value)
template <class K, class V>
using ordered_map = tree<K, V, less<K>, rb_tree_tag,
tree_order_statistics_node_update>;
int main() {
ordered_set<int> s;
for (int x : {5, 1, 8, 3, 9}) s.insert(x); // s = {1, 3, 5, 8, 9}
cout << *s.find_by_order(2) << '\n'; // 5
cout << s.order_of_key(6) << '\n'; // 3
ordered_map<string, int> score;
score["dung"] = 7;
score["an"] = 9;
score["binh"] = 4;
auto it = score.find_by_order(1); // 2nd key in sorted order
cout << it->first << ' ' << it->second << '\n'; // binh 4
cout << score.order_of_key("c") << '\n'; // 2 (an, binh)
}
Ý nghĩa các tham số của tree<Key, Mapped, Cmp, Tag, NodeUpdate>:
| Tham số | Giá trị thường dùng | Ý nghĩa |
|---|---|---|
Key |
int, pair<int,int> |
kiểu khoá |
Mapped |
null_type hoặc V |
null_type cho set, kiểu giá trị cho map |
Cmp |
less<Key> |
hàm so sánh; greater<Key> để sắp giảm dần |
Tag |
rb_tree_tag |
cây đỏ đen (còn splay_tree_tag, ov_tree_tag nhưng chậm hơn) |
NodeUpdate |
tree_order_statistics_node_update |
dữ liệu phụ ở nút; đây là thứ bật find_by_order |
Mọi hàm quen thuộc của std::set vẫn có: insert, erase (theo khoá hoặc iterator), find, lower_bound, upper_bound, begin, end, size, duyệt bằng for.
Multiset với k-th element online
Chương trình đọc thao tác + x, - x, ? k, # x như ví dụ chạy tay. Bản Python dùng Fenwick Tree trên giá trị đã nén toạ độ, vì Python không có pb_ds (xem mục Python bên dưới).
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
// multiset of ints: each element is (value, unique id)
using ordered_multiset = tree<pair<int, int>, null_type, less<pair<int, int>>,
rb_tree_tag, tree_order_statistics_node_update>;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> q;
ordered_multiset s;
int nextId = 0;
while (q--) {
char op;
int x;
cin >> op >> x;
if (op == '+') { // insert one copy of x
s.insert({x, nextId++});
} else if (op == '-') { // erase ONE copy of x (if any)
auto it = s.lower_bound({x, INT_MIN});
if (it != s.end() && it->first == x) s.erase(it);
} else if (op == '?') { // x-th smallest, 1-indexed
if (x < 1 || x > (int)s.size()) cout << -1 << '\n';
else cout << s.find_by_order(x - 1)->first << '\n';
} else { // '#': how many elements < x
cout << s.order_of_key({x, INT_MIN}) << '\n';
}
}
}
import sys
class FenwickOrderedMultiset:
"""Multiset over values known in advance (offline compression)."""
def __init__(self, values):
self.vals = sorted(set(values))
self.idx = {v: i + 1 for i, v in enumerate(self.vals)}
self.n = len(self.vals)
self.bit = [0] * (self.n + 1)
self.cnt = [0] * (self.n + 1)
self.size = 0
self.log = max(1, self.n.bit_length())
def _add(self, i, d):
while i <= self.n:
self.bit[i] += d
i += i & -i
def insert(self, v):
i = self.idx[v]
self.cnt[i] += 1
self.size += 1
self._add(i, 1)
def erase_one(self, v):
i = self.idx.get(v)
if i is not None and self.cnt[i] > 0:
self.cnt[i] -= 1
self.size -= 1
self._add(i, -1)
def count_less(self, v):
# number of elements < v: prefix sum up to the largest rank with value < v
lo, hi = 0, self.n
while lo < hi: # first rank whose value >= v
mid = (lo + hi) // 2
if self.vals[mid] < v:
lo = mid + 1
else:
hi = mid
i, s = lo, 0
while i > 0:
s += self.bit[i]
i -= i & -i
return s
def kth(self, k):
# k-th smallest (1-indexed) by binary lifting on the Fenwick tree
pos = 0
for b in range(self.log, -1, -1):
nxt = pos + (1 << b)
if nxt <= self.n and self.bit[nxt] < k:
pos = nxt
k -= self.bit[nxt]
return self.vals[pos] # rank pos + 1 has index pos in vals
def main():
data = sys.stdin.buffer.read().split()
q = int(data[0])
ops = [(data[1 + 2 * i].decode(), int(data[2 + 2 * i])) for i in range(q)]
ms = FenwickOrderedMultiset([x for op, x in ops if op == '+'])
out = []
for op, x in ops:
if op == '+':
ms.insert(x)
elif op == '-':
ms.erase_one(x)
elif op == '?':
out.append(ms.kth(x) if 1 <= x <= ms.size else -1)
else:
out.append(ms.count_less(x))
print("\n".join(map(str, out)))
main()
Input (đúng ví dụ chạy tay):
9
+ 5
+ 2
+ 5
+ 8
? 3
# 5
- 5
? 3
? 4
Output của cả hai chương trình:
5
1
8
-1
Đếm nghịch thế
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
// multiset emulation: store (value, unique index) so equal values never collide
using ordered_multiset = tree<pair<int, int>, null_type, less<pair<int, int>>,
rb_tree_tag, tree_order_statistics_node_update>;
int main() {
int n;
cin >> n;
ordered_multiset s;
long long inversions = 0;
for (int j = 0; j < n; j++) {
int x;
cin >> x;
// elements seen so far that are <= x: all pairs (v, i) < (x, INT_MAX)
int notGreater = s.order_of_key({x, INT_MAX});
inversions += (long long)s.size() - notGreater; // previous elements > x
s.insert({x, j});
}
cout << inversions << '\n';
}
import sys
from bisect import bisect_left
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = list(map(int, data[1:1 + n]))
# coordinate compression: value -> rank in 1..m
vals = sorted(set(a))
m = len(vals)
bit = [0] * (m + 1) # Fenwick tree over ranks, bit counts how many seen
def add(i):
while i <= m:
bit[i] += 1
i += i & -i
def prefix(i): # number of seen elements with rank <= i
s = 0
while i > 0:
s += bit[i]
i -= i & -i
return s
inversions = 0
for j, x in enumerate(a):
r = bisect_left(vals, x) + 1
inversions += j - prefix(r) # previous elements with value > x
add(r)
print(inversions)
main()
Với input 5 / 4 2 4 1 3, cả hai in 6. Bài này chỉ cần đếm nên Fenwick (cả C++) vừa nhanh vừa ít bộ nhớ hơn; ordered_set thắng khi giá trị không biết trước (không nén offline được) hoặc cần cả find_by_order.
gp_hash_table với hàm băm chống hack
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
// splitmix64 with a random seed chosen at runtime: anti-hack hash
struct SplitMix64Hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15ULL;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t SEED =
chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + SEED);
}
};
int main() {
gp_hash_table<long long, int, SplitMix64Hash> cnt; // open addressing
for (long long x : {7LL, 1000000000000LL, 7LL, -3LL, 7LL}) cnt[x]++;
cout << cnt[7] << ' ' << cnt[-3] << ' ' << cnt.size() << '\n'; // 3 1 3
cout << (cnt.find(42) == cnt.end()) << '\n'; // 1
cc_hash_table<int, int, SplitMix64Hash> other; // chaining variant, same API
other[5] = 10;
cout << other[5] << '\n'; // 10
}
Vì sao cần hàm băm riêng: hàm băm mặc định của số nguyên là hàm đồng nhất (), còn gp_hash_table dùng kích thước bảng là luỹ thừa của và lấy các bit thấp. Chỉ cần cho toàn khoá là bội của là mọi khoá rơi vào cùng một ô, mỗi thao tác thành . Trộn bit bằng splitmix64 với seed ngẫu nhiên lúc chạy khiến người ra test không thể biết trước khoá nào va chạm (cùng ý tưởng với Thuật toán ngẫu nhiên). Lưu ý gp_hash_table không có count; dùng find(x) != end().
Hàng đợi ưu tiên có join và modify
#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;
using MaxHeap = __gnu_pbds::priority_queue<int>; // default: max-heap, pairing_heap_tag
int main() {
MaxHeap a, b;
for (int x : {3, 9, 4}) a.push(x);
for (int x : {7, 1}) b.push(x);
a.join(b); // move all of b into a, b becomes empty
cout << a.size() << ' ' << b.size() << ' ' << a.top() << '\n'; // 5 0 9
auto it = a.push(2);
a.modify(it, 100); // change a value through its point_iterator
cout << a.top() << '\n'; // 100
a.erase(it); // erase an arbitrary element
cout << a.top() << '\n'; // 9
}
join dùng cho bài gộp heap (mergeable heap): ví dụ gộp tập của các con lên cha trên cây, hoặc gộp hai nhóm khi hai thành phần DSU hợp lại. Với std::priority_queue ta phải gộp nhỏ vào lớn ( tổng), còn pairing heap gộp trong .
modify cho phép Dijkstra với decrease-key: mỗi đỉnh chỉ có tối đa một nút trong heap, không có "bản ghi cũ" phải bỏ qua. Đồ thị ví dụ (vô hướng, nguồn là đỉnh 1):
graph weighted 5 6 1 2 4 1 3 1 3 2 2 2 4 5 3 4 8 4 5 3 path green 1 3 2 4 5
| Bước | Lấy ra | Thao tác trên heap |
|---|---|---|
| 1 | push , push |
|
| 2 | : modify đỉnh 2 thành ; push |
|
| 3 | : modify đỉnh 4 thành |
|
| 4 | push |
|
| 5 | heap rỗng, dừng |
Khoảng cách: 0 3 1 8 11.
#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;
using ll = long long;
// min-heap by distance: greater<> on pair (dist, vertex)
using Heap = __gnu_pbds::priority_queue<pair<ll, int>, greater<pair<ll, int>>,
__gnu_pbds::pairing_heap_tag>;
int main() {
int n, m;
cin >> n >> m;
vector<vector<pair<int, int>>> adj(n + 1);
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
const ll INF = LLONG_MAX;
vector<ll> dist(n + 1, INF);
vector<Heap::point_iterator> where(n + 1); // handle to v's node in heap
vector<bool> inHeap(n + 1, false);
Heap pq;
dist[1] = 0;
where[1] = pq.push({0, 1});
inHeap[1] = true;
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
inHeap[u] = false;
for (auto [v, w] : adj[u]) {
if (d + w < dist[v]) {
dist[v] = d + w;
if (inHeap[v]) {
pq.modify(where[v], {dist[v], v}); // decrease-key in place
} else {
where[v] = pq.push({dist[v], v});
inHeap[v] = true;
}
}
}
}
// each vertex enters the heap at most once (no stale entries)
for (int v = 1; v <= n; v++) cout << (dist[v] == INF ? -1 : dist[v]) << " \n"[v == n];
}
Thực tế bản Dijkstra thông thường với std::priority_queue và "bỏ qua bản ghi cũ" thường nhanh ngang hoặc nhanh hơn, vì std::priority_queue là mảng liên tục. Decrease-key đáng dùng khi bộ nhớ chật (heap chỉ thay vì ) hoặc khi đồ thị rất dày.
Custom node update (tóm tắt)
tree_order_statistics_node_update chỉ là một chính sách lưu "kích thước cây con". Ta tự viết được chính sách khác, ví dụ lưu tổng khoá trong cây con để trả lời "tổng các phần tử " trong :
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
// Custom node update: every node stores the sum of keys in its subtree.
template <class NodeCItr, class NodeItr, class Cmp, class Alloc>
struct sum_update {
typedef long long metadata_type; // extra data stored in each node
// called bottom-up whenever node 'it' changes; recompute from children
void operator()(NodeItr it, NodeCItr endIt) {
NodeItr l = it.get_l_child(), r = it.get_r_child();
long long s = **it; // key of this node (for a set, **it is the key)
if (l != endIt) s += l.get_metadata();
if (r != endIt) s += r.get_metadata();
const_cast<long long&>(it.get_metadata()) = s;
}
// sum of keys strictly less than x: walk down from the root
long long prefix_sum(int x) {
long long res = 0;
NodeCItr it = node_begin();
while (it != node_end()) {
NodeCItr l = it.get_l_child();
if (**it < x) {
res += **it;
if (l != node_end()) res += l.get_metadata();
it = it.get_r_child();
} else {
it = l;
}
}
return res;
}
virtual NodeCItr node_begin() const = 0;
virtual NodeCItr node_end() const = 0;
virtual ~sum_update() {}
};
int main() {
tree<int, null_type, less<int>, rb_tree_tag, sum_update> s;
for (int x : {5, 1, 8, 3, 9}) s.insert(x);
cout << s.prefix_sum(6) << '\n'; // 1 + 3 + 5 = 9
s.erase(3);
cout << s.prefix_sum(100) << '\n'; // 1 + 5 + 8 + 9 = 23
}
Cú pháp khá rườm rà; khi cần dữ liệu phụ phức tạp hơn (cộng lazy, đảo đoạn), tự cài Treap thường dễ kiểm soát hơn.
rope (tóm tắt)
#include <bits/stdc++.h>
#include <ext/rope>
using namespace std;
using namespace __gnu_cxx;
int main() {
rope<int> r;
for (int i = 1; i <= 6; i++) r.push_back(i); // 1 2 3 4 5 6
// cut the block [1, 3) (values 2 3) and paste it at the end
rope<int> block = r.substr(1, 2);
r.erase(1, 2); // 1 4 5 6
r.insert(r.size(), block); // 1 4 5 6 2 3
for (int x : r) cout << x << ' ';
cout << '\n';
cout << r[4] << '\n'; // 2 (random access by position)
}
Output: 1 4 5 6 2 3 rồi 2. rope hợp với bài "cắt một đoạn dán sang chỗ khác" hoặc lưu nhiều phiên bản (sao chép rope tốn vì chia sẻ nút). Hằng số lớn và không hỗ trợ đảo đoạn hay truy vấn tổng; bài có các thao tác đó nên dùng treap ngầm định.
Python: không có pb_ds
Python không có cây thống kê thứ tự trong thư viện chuẩn, và sortedcontainers thường không được cài trên judge. Hai lựa chọn:
- Fenwick trên giá trị nén (như lớp
FenwickOrderedMultisetở trên): nhanh, mỗi thao tác, nhưng cần biết trước mọi giá trị (đọc hết input rồi nén). - List đã sắp +
bisect: đơn giản nhất, hợp với cỡ vìinsortvàpopdịch mảng bằngmemmoverất nhanh dù về lý thuyết là .
from bisect import bisect_left, insort
a = [] # always kept sorted
for x in [5, 2, 5, 8]:
insort(a, x) # O(n) shift, but a fast memmove
print(a[3 - 1]) # 3rd smallest: 5
print(bisect_left(a, 5)) # count of elements < 5: 1
a.pop(bisect_left(a, 5)) # erase one copy of 5
print(a) # [2, 5, 8]
Hàng đợi ưu tiên trong Python là heapq (không có join/modify), bảng băm là dict. Xem thêm Python cho lập trình thi đấu.
Độ phức tạp
| Cấu trúc | Thao tác | Thời gian | Ghi chú |
|---|---|---|---|
tree (rb_tree_tag) |
insert, erase, find, lower_bound |
như std::set |
|
find_by_order, order_of_key |
đi một đường từ gốc xuống lá | ||
gp_hash_table |
[], find, insert, erase |
trung bình | xấu nhất nếu bị hack hàm băm |
priority_queue (pairing heap) |
push, top, join |
||
pop, erase |
khấu hao | ||
modify |
khấu hao | giảm khoá thực tế rất nhanh | |
rope |
insert, erase, substr ở giữa |
hằng số lớn | |
r[i] |
không phải như vector |
Lý giải: cây đỏ đen cao không quá ; mỗi nút lưu thêm kích thước cây con, giá trị này chỉ đổi ở các nút trên đường chèn/xoá và các nút bị xoay (tối đa nút), nên find_by_order và order_of_key chỉ cần một lượt đi xuống. Pairing heap gộp hai heap bằng cách gắn gốc nhỏ hơn làm con gốc kia (), độ phức tạp pop là khấu hao.
Bộ nhớ: tất cả . Tuy nhiên mỗi nút của tree gồm khoá, ba con trỏ (cha, trái, phải), màu và metadata: với pair<int,int> một nút chiếm byte (đo bằng sizeof trên GCC 14, chưa kể phần quản lý của bộ cấp phát), nên phần tử tốn cỡ đến MB. gp_hash_table cấp phát bảng gấp đôi lên khi đầy nên có lúc dùng gấp vài lần số phần tử.
⚠️ Lỗi thường gặp
- Dùng
less_equalđể làm multiset. Nhiều tài liệu khuyêntree<int, null_type, less_equal<int>, ...>để chứa phần tử trùng. Triệu chứng:find(x)luôn trả vềend(),erase(x)âm thầm không xoá gì, cònlower_boundvàupper_boundbị đổi vai cho nhau. Đã kiểm tra trên GCC 14: chèn rồierase(2)thì size vẫn là ,*lower_bound(2)ra . Lý do:less_equalkhông phải thứ tự ngặt, cây không bao giờ thấy hai khoá "bằng nhau" (!cmp(a,b) && !cmp(b,a)không bao giờ đúng). Cách tránh: dùng cặp(giá trị, id duy nhất)và xoá bằng iterator từlower_bound({x, INT_MIN}). - Chỉ có trên GCC.
pb_dsvàropelà phần mở rộng của libstdc++: MSVC không có, Clang với libc++ (mặc định trên macOS) báo lỗi không tìm thấy header. Judge chạy GCC thì ổn; trên máy Mac cần càig++thật (Homebrewgcc), vì lệnhg++mặc định thực chất là Clang. find_by_order(k)với size trả vềend(). Giải tham chiếu*s.find_by_order(k)lúc đó là hành vi không xác định (in rác hoặc crash). Luôn kiểm trak < s.size(). Nhớfind_by_orderđếm từ : phần tử nhỏ thứ (đếm từ ) làfind_by_order(k - 1).order_of_keytrả vềsize_tkhông dấu. Viếts.order_of_key(x) - 1khi kết quả là sẽ tràn thành số khổng lồ. Ép sangint/long longtrước khi trừ. Cũng nhớorder_of_key(x)đếm phần tử nhỏ hơn hẳn ; muốn thì dùngorder_of_key(x + 1)(số nguyên) hoặc{x, INT_MAX}(với cặp).- Hằng số lớn, tưởng là đủ.
ordered_setchậm hơnstd::setkhoảng đến lần và chậm hơn Fenwick nhiều lần. Với thao tác trong giây có thể TLE. Nếu giá trị biết trước (nén được offline), dùng Fenwick Tree với tìm kiếm nhị phân trên cây. gp_hash_tablevới hàm băm mặc định bị hack. Trên Codeforces và các kỳ có hack, test toàn bội của luỹ thừa làm mọi thao tác thành , TLE. Luôn kèm hàm băm splitmix64 có seed ngẫu nhiên như trên. Với khoá làpair, tự gộp thànhuint64_trồi băm.- Quên rằng
modify/erasecầnpoint_iteratorcòn hợp lệ. Sau khipopphần tử đó, tay cầm cũ không còn dùng được; gọimodifylên nó là hành vi không xác định. Theo dõi phần tử nào còn trong heap (như mảnginHeapở bản Dijkstra). using namespace __gnu_pbds;đè tênpriority_queue. Khi đãusing namespace std;vàusing namespace __gnu_pbds;thìpriority_queuetrở nên nhập nhằng, báo lỗi biên dịch. Hãy viết đầy đủstd::priority_queuehoặc__gnu_pbds::priority_queue.
Biến thể / Mở rộng
- Sắp giảm dần: đổi
less<T>thànhgreater<T>, khi đófind_by_order(0)là phần tử lớn nhất. splitvàjoincủatree:s.split(x, t)chuyển mọi phần tử sangt;s.join(t)nối lại (dùng khi mọi khoá củatlớn hơn mọi khoá củas, đúng tình huống sau một lầnsplit). Nhanh hơn nhiều so với chèn lại từng phần tử, hợp với bài tách/ghép tập theo ngưỡng giá trị.- Trung vị động: giữ tập bằng
ordered_multiset, trung vị làfind_by_order((size - 1) / 2). Cách khác không cầnpb_dslà hai heap (xem Tham lam với heap và Heap). - Khi cần nhiều hơn: truy vấn theo đoạn chỉ số, cập nhật lazy, đảo đoạn thì dùng Segment Tree hoặc Treap. Phần tử nhỏ thứ trên một đoạn con của mảng dùng Persistent Segment Tree hoặc Wavelet Tree.
Bài tập luyện
- Trung vị (icpc22mbh) (Trung bình) Thêm, xoá một bản sao và hỏi trung vị online; luyện mẹo multiset bằng cặp
(giá trị, id)cùngfind_by_order. - Truy vấn giá (tnhsg1026_b) (Trung bình) Hỏi mức giá phân biệt nhỏ thứ khi danh sách thay đổi;
ordered_setcác giá phân biệt kèm bộ đếm số lượng mỗi giá. - Trung Vị Cửa Sổ Trượt (swmedian) (Khó) Trung vị mọi cửa sổ độ dài : mỗi bước chèn một phần tử, xoá một phần tử và gọi
find_by_order. - Bắn bi (thhv23_marbles) (Khó) Tìm viên bi còn sống thứ rồi xoá nó;
ordered_setcác chỉ số còn sống thay cho Fenwick. - Xếp hạng lại (vtc03_rank) (Khó) Đếm nghịch thế và, với mỗi học sinh, số người cao hơn bên trái và thấp hơn bên phải bằng
order_of_key; nên so sánh tốc độ với Fenwick.
Bình luận