blob: 734bf918510f542f5e4ed7fec50b5c2bf62ad5ad (
plain)
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
|
#include <ext/pb_ds/priority_queue.hpp>
template<typename T>
using pQueue = __gnu_pbds::priority_queue<T>; //<T, greater<T>>
auto it = pq.push(5); // O(1)
pq.modify(it, 6); // O(log n)
pq.erase(it); // O(log n)
pq.join(pq2); // O(1)
pq.swap(pq2); // O(1)
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<typename T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag,
tree_order_statistics_node_update>;
T.order_of_key(x); // number of elements strictly less than x
auto it = T.find_by_order(k); // k-th element
constexpr uint64_t RNG = ll(2e18 * acos(-1)) | 199; // random odd
template<typename T> struct chash {
size_t operator()(T o) const {
return __builtin_bswap64(hash<T>()(o) * RNG);
}};
template<typename K, typename V>
using hashMap = gp_hash_table<K, V, chash<K>>;
template<typename T>
using hashSet = gp_hash_table<T, null_type, chash<T>>;
|
