ii. Ordered Set and PBDS

std::set can’t answer “$k$-th smallest” or “how many are less than $x$”. GNU’s policy-based data structures (PBDS) can, in $O(\log n)$. They also provide a meldable heap with decrease-key and a fast hash table, and __gnu_cxx::rope gives a sequence with $O(\log n)$ splits.

Order-statistics tree

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
oset<int> s;
s.insert(x); s.erase(x);
*s.find_by_order(k);      // k-th smallest, 0-indexed (end() if k >= size)
s.order_of_key(x);        // number of elements < x

Multiset: store pair<T, int> with a unique id; order_of_key({x, INT_MIN}) counts elements below $x$, and erase via s.erase(s.lower_bound({x, INT_MIN})). Using less_equal as the comparator “works” for inserts but breaks find, erase and lower_bound semantics; avoid it.

Proof: the (value, id) pair encoding correctly simulates a multiset

Every stored key is (v, id) with id unique per inserted element (e.g. a counter), compared lexicographically, so no two stored keys ever collide — a plain tree (which rejects duplicates) can hold arbitrarily many equal-$v$ elements this way. The sentinel (x, \text{INT\_MIN}) is lexicographically smaller than every real pair with first component $x$ (since id is never less than INT_MIN in practice) and larger than every pair with first component $<x$, so order_of_key({x, INT_MIN}) counts exactly the stored pairs with first component $<x$ — the logical count of elements $<x$ in the multiset, independent of how many copies of each value are present. The same sentinel trick makes lower_bound({x, INT_MIN}) land on the first stored element with value $\ge x$ when one exists (needed for a well-defined erase-by-value), since it sorts just before any pair with first component $x$. $■$

Map with order statistics: tree<K, V, less<K>, rb_tree_tag, tree_order_statistics_node_update>.

Custom node updates: PBDS lets you write your own node_update to maintain subtree aggregates (sums, max) in the tree. A treap is usually easier.

Faster alternatives when values are known

Approach	Query	Notes
PBDS tree	$O(\log n)$, big constant	online, any comparable keys
Fenwick over compressed values	$O(\log n)$, 5-10x faster	needs all values up front
Fenwick with bitwise descent	$k$-th in one $O(\log n)$ walk	see Fenwick Tree
segment tree over values	$O(\log n)$	supports more aggregates (sum of $k$ smallest)
treap with sizes	$O(\log n)$	fully customisable, splits and merges
sqrt decomposition over values	$O(\sqrt{n})$	simplest to reason about, when $\log n$ isn’t needed
64-ary bit tree	predecessor/successor in $O({\log }_{64}U)$	integers only, no $k$-th

Typical uses

Problem	Operation
inversions online	insert right to left, order_of_key
sliding window median / $k$-th	insert and erase as the window moves
Josephus elimination order	find_by_order((pos + k - 1) % size) and erase
rank of each element when inserted	order_of_key before insert
count values in $[l,r]$	order_of_key(r + 1) - order_of_key(l)

PBDS priority queue

#include <ext/pb_ds/priority_queue.hpp>
using PQ = __gnu_pbds::priority_queue<ll, greater<ll>, __gnu_pbds::pairing_heap_tag>;   // min-heap
PQ q; auto it = q.push(5);
q.modify(it, 3);          // decrease (or increase) key through the iterator
q.erase(it);
q.join(other);            // meld in O(1); other becomes empty

Pairing heap: $O(1)$ push and join, $O(\log n)$ amortized pop/modify. It enables Dijkstra with real decrease-key (rarely faster than lazy deletion in practice) and meldable heaps for “merge the queues of two children” problems.

Proof: pairing heap push/join are $O(1)$; pop/modify are $O(\log n)$ amortized

A pairing heap is a heap-ordered multiway tree (every node’s key $\le$ its children’s). push(x) makes $x$ a new singleton tree and links it with the root (attaches the larger-rooted tree as a new leftmost child of the smaller) — one pointer operation, $O(1)$. join of two heaps is the same single link of their two roots, also $O(1)$; modify (decrease-key) detaches the node’s subtree and re-links it as a new child of the root, $O(1)$ for the structural change itself. pop removes the root (whose children become a list of disjoint trees) and must restore a single tree by pairwise-linking that list — the step where real work happens. The amortized $O(\log n)$ bound for pop/modify is a genuinely delicate potential-function argument (Fredman, Sedgewick, Sleator, Tarjan 1986) that is not reproduced here; the $O(1)$ bounds above are the parts that follow directly from the structure.

Rope

#include <ext/rope>
using namespace __gnu_cxx;
rope<int> r;
r.push_back(x); r.insert(pos, x); r.erase(pos, len);
rope<int> piece = r.substr(pos, len);     // shares nodes: O(log n)
r.insert(pos, piece); r[i];

Copying a rope is $O(1)$ (persistent, shared structure), so “copy a segment and paste it somewhere else” or “keep every version” problems become one-liners. It’s 2-5x slower than a hand-written implicit treap. Memory can blow up with many versions.

Proof: rope copy is $O(1)$, split/insert are $O(\log n)$

rope is internally a balanced binary tree (an implicit treap) over immutable leaf chunks of characters, with each internal node caching its subtree’s size. Copying a rope (or taking substr) only needs to copy the $O(\log n)$ nodes on the paths that get split — every leaf chunk is shared, never duplicated, so the copy is $O(\log n)$ work for a substr/split and genuinely $O(1)$ for copying the whole rope (no split needed, just one new root pointer to the same tree). Because nodes are never mutated in place (an operation that would touch a node instead rebuilds the $O(\log n)$ nodes on the path to it, like any persistent treap), an older copy’s tree is never disturbed by later operations on a new copy — which is exactly what makes “keep every version” safe. $■$

Portability

PBDS and rope are libstdc++ extensions: they work with GCC on Codeforces, AtCoder and ICPC systems, but not with MSVC or libc++. Keep a treap in the library as a fallback (Treaps).

Other PBDS containers

gp_hash_table is a fast open-addressing hash map — typically 3-5× faster than unordered_map and, with a randomised hash (splitmix64, time-seeded), resistant to anti-hash tests (the default integer hash is the identity, trivially hackable). It’s the usual pairing with the order-statistics tree when a problem needs both a fast map and a fast ordered structure, and shares the same GCC-only portability caveat above.