Policy-Based Data Structures (GNU PBDS)

Quick Revisit: $O(\log n)$ rank queries on a dynamic set—find_by_order(k) for the $k$-th smallest, order_of_key(x) for count-less-than. Backed by an augmented red-black tree that stores subtree sizes. The classic trap: it's a set, not a multiset. For duplicates, pair each value with a unique index (pair<int,int>). (Practice problems)

Difficulty: CF 1500–1900 · Prereqs: Set & Multiset, Fenwick Tree

---

Why This Exists

PBDS exists for one narrow but common request: maintain a dynamic set and ask for ranks as the set changes.

std::set already gives you insertion, deletion, and membership in $O(\log n)$, but it cannot answer two questions that show up constantly in contest problems:

• "What is the element at rank $k$?"
• "How many elements are strictly less than $x$?"

You can force the issue with std::advance(s.begin(), k), but that makes each rank query linear. A Fenwick tree over compressed values is another option—often fast enough—but the setup is bulky: coordinate compression, index mapping, and a few extra lines before the actual logic even starts.

GNU PBDS gives you the missing piece directly. Its augmented red-black tree keeps subtree sizes at every node, so find_by_order(k) and order_of_key(x) both run in $O(\log n)$: it behaves like std::set with order statistics built in.

Walkthrough

To see both methods in action, insert the elements 10, 20, 30, 50, 40 into an ordered set. After each insertion, the 0-indexed rank of every element is shown.

After insert(10):
        [10]
  rank:   0

After insert(20):
        [10, 20]
  rank:   0   1

After insert(30):
        [10, 20, 30]
  rank:   0   1   2

After insert(50):
        [10, 20, 30, 50]
  rank:   0   1   2   3

After insert(40):
        [10, 20, 30, 40, 50]
  rank:   0   1   2   3   4

  find_by_order(2) --> iterator to 30
  order_of_key(35) --> 3  (elements < 35: {10, 20, 30})
  order_of_key(40) --> 3  (elements < 40: {10, 20, 30})
  order_of_key(41) --> 4  (elements < 41: {10, 20, 30, 40})

The Two Operations

find_by_order(k) returns an iterator to the $k$-th element, 0-indexed. If $k\ge n$, it returns end().

order_of_key(x) returns the number of elements strictly less than $x$.

These are inverse views of the same ordering. If the set contains distinct values $a_0<a_1<\cdots <a_{n-1}$, then *find_by_order(i) == a_i and order_of_key(a_i) == i.

Memory aid: "Find BY order, Order OF key"—each method is named by what it takes as input. find_by_order(k) takes a rank. order_of_key(x) takes a key.

Under the Hood

How an order-statistic tree works. Every node in the augmented BST stores the size of its subtree. find_by_order(k) walks left or right based on those subtree sizes, and order_of_key(x) accumulates the sizes of left subtrees it skips over. Without that picture, the methods feel magical.

    Internal BST with subtree sizes:

            (30) sz=5
           /          \
       (10) sz=2    (50) sz=2
          \          /
        (20)sz=1  (40)sz=1

    order_of_key(35):
      at 30: 35>30, add left_sz+1 = 2+1 = 3, go right
      at 50: 35<50, go left
      at 40: 35<40, go left
      null --> return 3
      Answer: 3 elements are strictly < 35

Coordinate compression is unnecessary with PBDS. Many rank-query problems involve values up to ${10}^9$ but only $n\le 2\times {10}^5$ distinct values. PBDS handles them directly—insert the real values, ask for ranks, and skip the compression bookkeeping entirely.

The pair trick for multisets is not just a hack. It exploits lexicographic pair comparison: {val, id} preserves value-based ordering while making every key unique. The second field must be unique, so use a timer or counter.

Why the C++ STL doesn't provide order statistics natively. Keeping subtree sizes up to date means touching the balancing logic on every rotation during insert and erase. The standard library keeps std::set minimal and generic, so it doesn't pay that memory and maintenance cost for everyone. PBDS solves the same problem with an explicit policy: opt in to the augmentation, and every node carries the extra field.

The trade-off: PBDS uses more memory and runs slower. Each PBDS node stores the key, three pointers, a color bit, and the subtree size—roughly 48 bytes on a 64-bit system. A Fenwick tree stores one int per bucket, so at $n={10}^6$ the comparison is roughly 48 MB versus 4 MB. The BIT also tends to be 2–3× faster because it is a flat array rather than a pointer-chasing tree.

When is the 5-line setup worth it? Use PBDS when you need a quick rank-query solution and the constraints are comfortable ($n\le 2\times {10}^5$, generous time limit). Roll your own BIT plus coordinate compression when you need range-sum queries, when $n$ is large and the time limit is tight, or when the judge doesn't support GCC extensions. In practice, PBDS covers most order-statistic problems; the remaining cases are usually better served by a BIT or segment tree.

With those trade-offs in mind, the recognition question is simple: when does a problem call for PBDS? Watch for these phrases:

Trigger	Translation
"$k$-th smallest"	find_by_order(k - 1)
"rank of element"	order_of_key(x) + 1 (1-indexed)
"dynamic order statistics"	ordered set with rank queries
"count of elements less than"	order_of_key(x)
"number of inversions"	insert elements, query ranks
"dynamic median"	maintain two ordered sets or one set + rank query

If the problem says "offline" and values are static, a Fenwick tree or merge-sort approach is often simpler. Reach for PBDS when the set is dynamic—insertions and deletions interleaved with queries.

When NOT to reach for this:

• Judge doesn't support GCC (__gnu_pbds is a GCC extension—won't compile on MSVC, Clang, or LeetCode)
• You need min/max/sum range queries, not rank queries—use Fenwick or segment tree
• You need efficient split/merge—use a treap
• Memory is very tight (~48 bytes/node vs ~4 bytes for BIT)
• Data is static (no insertions)—just sort and binary search

Header and Typedef

#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 of distinct integers.
typedef tree<
    int,                        // key type
    null_type,                  // mapped type (null_type = set, not map)
    less<int>,                  // comparator
    rb_tree_tag,                // red-black tree
    tree_order_statistics_node_update  // augment with subtree sizes
> ordered_set;

Codeforces / competitive note: This compiles on GCC (g++) which is available on CF, AtCoder, and most online judges. It does not work on MSVC or Clang without the GCC extensions.

Basic Operations

ordered_set os;

os.insert(10);
os.insert(20);
os.insert(30);
os.insert(40);
os.insert(50);

// find_by_order(k): iterator to the k-th element (0-indexed)
cout << *os.find_by_order(0) << "\n"; // 10
cout << *os.find_by_order(2) << "\n"; // 30
cout << *os.find_by_order(4) << "\n"; // 50

// order_of_key(x): count of elements strictly less than x
cout << os.order_of_key(30) << "\n";  // 2
cout << os.order_of_key(35) << "\n";  // 3
cout << os.order_of_key(1)  << "\n";  // 0

// erase by value
os.erase(30);
cout << *os.find_by_order(2) << "\n"; // 40  (30 is gone)
cout << os.order_of_key(40) << "\n";  // 2

// erase by iterator
auto it = os.find_by_order(0);
os.erase(it);
cout << *os.find_by_order(0) << "\n"; // 20

Ordered Multiset (Duplicate Keys)

tree<int, ...> behaves like std::set—duplicates are silently ignored on insert. The standard trick is to store pair<int, int> where the second component is a unique tie-breaker (e.g., insertion index). It exploits lexicographic comparison of pairs: {val, id} ensures unique keys while preserving value-based ordering. The second field must be unique (use a timer/counter).

typedef tree<
    pair<int, int>,
    null_type,
    less<pair<int, int>>,
    rb_tree_tag,
    tree_order_statistics_node_update
> ordered_multiset;

ordered_multiset oms;
int timer = 0;

auto ms_insert = [&](int x) {
    oms.insert({x, timer++});
};

auto ms_erase = [&](int x) {
    // erase one occurrence: find the first pair with key x
    auto it = oms.lower_bound({x, 0});
    if (it != oms.end() && it->first == x)
        oms.erase(it);
};

auto ms_order_of_key = [&](int x) -> int {
    // count of elements strictly less than x
    return (int)oms.order_of_key({x, 0});
};

auto ms_find_by_order = [&](int k) -> int {
    return oms.find_by_order(k)->first;
};

// Example
ms_insert(5); ms_insert(5); ms_insert(3); ms_insert(8);
// contents: {3, 5, 5, 8}

cout << ms_order_of_key(5)     << "\n"; // 1 (only 3 < 5)
cout << ms_order_of_key(6)     << "\n"; // 3 ({3, 5, 5} < 6)
cout << ms_find_by_order(1)    << "\n"; // 5
cout << ms_find_by_order(2)    << "\n"; // 5

Custom Comparator

For a descending ordered set (largest element at rank 0):

typedef tree<
    int,
    null_type,
    greater<int>,               // descending order
    rb_tree_tag,
    tree_order_statistics_node_update
> desc_ordered_set;

desc_ordered_set ds;
ds.insert(10); ds.insert(30); ds.insert(20);
cout << *ds.find_by_order(0) << "\n";  // 30 (largest)
cout << ds.order_of_key(25)  << "\n";  // 1  (only 30 > 25)

Warning: With greater<int>, order_of_key(x) returns the count of elements strictly greater than $x$—it always counts elements that come before $x$ in the comparator's ordering.

Pre-Code Sanity Check

Before you start typing, check the constraints and the platform. Does the judge support GCC extensions? Do you need duplicates—and if so, are you using pair<int,int> with a unique timer? Are you treating order_of_key as "strictly less than" rather than ≤? Did you guard find_by_order(k) against end()? Would a BIT with coordinate compression actually be faster here?

---

Complexity

Every PBDS operation matches std::set at $O(\log n)$, including the two order-statistic extras.

Operation	Time	Space
insert	$O(\log n)$	$O(n)$
erase	$O(\log n)$
find_by_order	$O(\log n)$
order_of_key	$O(\log n)$
find / lower_bound / upper_bound	$O(\log n)$

The constant factor is roughly 2–3× that of std::set due to the extra subtree-size bookkeeping, but for $n\le {10}^6$ this is rarely a problem on modern judges with 2–3 second time limits.

Pattern 1: Count Inversions

An inversion in array $a$ is a pair $(i,j)$ with $i<j$ and $a_i>a_j$. Process elements left to right; for each $a_i$, the count of previously inserted elements greater than $a_i$ equals the number of new inversions it contributes.

long long count_inversions(const vector<int>& a) {
    ordered_set os;
    long long inv = 0;
    for (int i = 0; i < (int)a.size(); i++) {
        // elements already in set that are > a[i]
        inv += i - os.order_of_key(a[i]);
        os.insert(a[i]);
    }
    return inv;
}

If duplicates exist, use the ordered_multiset variant:

long long count_inversions_dup(const vector<int>& a) {
    ordered_multiset oms;
    int timer = 0;
    long long inv = 0;
    for (int i = 0; i < (int)a.size(); i++) {
        // elements > a[i]: total inserted so far minus those <= a[i]
        // order_of_key({a[i]+1, 0}) counts elements strictly less than (a[i]+1, 0)
        //   = elements with value <= a[i]
        inv += i - (int)oms.order_of_key({a[i] + 1, 0});
        oms.insert({a[i], timer++});
    }
    return inv;
}

Trace on [3, 1, 2]:

Array: [3, 1, 2]

i=0, a[i]=3:
  oms = {}
  order_of_key({4, 0}) = 0   (nothing in set)
  inv += 0 - 0 = 0           inv = 0
  insert {3, 0}              oms = {(3,0)}

i=1, a[i]=1:
  oms = {(3,0)}
  order_of_key({2, 0}) = 0   (no element < (2,0))
  inv += 1 - 0 = 1           inv = 1     <-- (3,1) is an inversion
  insert {1, 1}              oms = {(1,1), (3,0)}

i=2, a[i]=2:
  oms = {(1,1), (3,0)}
  order_of_key({3, 0}) = 1   ((1,1) < (3,0))
  inv += 2 - 1 = 1           inv = 2     <-- (3,2) is an inversion

Total inversions: 2
Verification: pairs (3,1) and (3,2) are the two inversions.

Complete Compilable Solution (Reads from stdin)

This handles duplicates and arbitrary values up to ${10}^9$. No coordinate compression needed—PBDS handles it directly.

#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;

typedef tree<
    pair<int, int>, null_type, less<pair<int, int>>,
    rb_tree_tag, tree_order_statistics_node_update
> ordered_multiset;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    ordered_multiset oms;
    int timer = 0;
    long long inv = 0;

    for (int i = 0; i < n; i++) {
        // Count elements already inserted that are > a[i].
        // order_of_key({a[i]+1, 0}) = count of elements with value <= a[i]
        //   (because pairs with value a[i] and any timer < 0 don't exist,
        //    so {a[i]+1, 0} is strictly greater than any {a[i], t}).
        // Elements > a[i] = (total inserted) - (elements <= a[i])
        inv += i - (int)oms.order_of_key({a[i] + 1, 0});
        oms.insert({a[i], timer++});
    }

    cout << inv << "\n";
    return 0;
}

Input format: First line is $n$, second line has $n$ space-separated integers. Output: A single integer—the inversion count.

Example: 3\n3 1 2 → output 2.

Why no coordinate compression? Unlike a BIT-based solution that needs values mapped to array indices, PBDS stores actual values in a balanced BST. It works with any comparable type—no mapping needed.

Pattern 2: $k$-th Smallest in a Stream

Maintain an ordered set (or multiset). After each insertion, answer "what is the $k$-th smallest?" in $O(\log n)$.

void kth_smallest_stream(const vector<int>& stream, int k) {
    ordered_multiset oms;
    int timer = 0;
    for (int x : stream) {
        oms.insert({x, timer++});
        if ((int)oms.size() >= k) {
            cout << oms.find_by_order(k - 1)->first << "\n";
        }
    }
}

Pattern 3: Dynamic Median

After each insertion, the median is the element at rank $\lfloor n/2\rfloor$ (0-indexed) for an odd-sized set, or rank $n/2-1$ for an even-sized set (lower median).

void dynamic_median(const vector<int>& a) {
    ordered_multiset oms;
    int timer = 0;
    for (int x : a) {
        oms.insert({x, timer++});
        int n = (int)oms.size();
        int median = oms.find_by_order((n - 1) / 2)->first;
        cout << median << "\n";
    }
}

Pattern 4: Range Rank Query (Count in [lo, hi])

Count elements in the closed interval $[lo,hi]$:

int count_in_range(ordered_set& os, int lo, int hi) {
    return os.order_of_key(hi + 1) - os.order_of_key(lo);
}

For the multiset variant:

int count_in_range_ms(ordered_multiset& oms, int lo, int hi) {
    return (int)oms.order_of_key({hi + 1, 0}) - (int)oms.order_of_key({lo, 0});
}

Pattern 5: Swap Distance (Minimum Adjacent Swaps to Sort)

The minimum number of adjacent swaps needed to sort a permutation equals its inversion count. Use Pattern 1 directly.

---

Edge Cases and Pitfalls

1. Duplicate keys are silently ignored. If you insert the same value twice into ordered_set, the second insert is a no-op. Use the pair<int, int> multiset trick for duplicates.

2. order_of_key returns count of strictly less, not ≤. To count elements $\le x$, use order_of_key(x + 1) (for integers).

3. find_by_order(k) with $k\ge n$ returns end(). Dereferencing end() is undefined behavior. Always check bounds.

4. No operator[]. You cannot write os[k]; use *os.find_by_order(k).

5. Not mergeable. Unlike some balanced BST libraries, PBDS tree does not support efficient split/merge (it has join, but that requires non-overlapping key ranges). For split/merge, use a treap.

6. Iteration order. Iterating with for (auto x : os) visits elements in comparator order (ascending for less<int>), same as std::set.

7. Memory. Each node stores key + subtree size + 3 pointers + color bit. Roughly 40–48 bytes per element on 64-bit systems. For $n={10}^6$ this is about 48 MB—usually fine but worth checking.

8. Judge availability. PBDS is a GCC extension (__gnu_pbds namespace), not standard C++. It compiles on:

   • Codeforces: ✓ (GCC available)
   • AtCoder: ✓ (GCC available)
   • USACO: ✓ (GCC available)
   • CSES: ✓ (GCC available)
   • LeetCode: ✗ (uses Clang, no __gnu_pbds)
   • HackerRank: varies—test before submitting

9. Compiler flags. PBDS requires at least -std=c++14 (for null_type; older GCC versions used null_mapped_type). Use -std=c++17 to be safe. The __gnu_pbds namespace triggers no warnings with -Wall, but it is a GCC extension—not part of the C++ standard, and it will not work with MSVC or Clang.

10. Performance vs. BIT. PBDS is roughly 2–3× slower than a Fenwick tree for equivalent order-statistic operations. The BIT is a flat array (cache-friendly); PBDS is a pointer-based tree (cache-unfriendly). For $n\le 2\times {10}^5$ this rarely matters, but for $n={10}^6$ with a tight time limit (1–2s), a BIT may be necessary.

11. Memory vs. BIT. PBDS uses ~48 bytes per node; a BIT uses ~4 bytes per element (one int). For $n={10}^6$: PBDS ≈ 48 MB, BIT ≈ 4 MB. With a 256 MB memory limit, both are fine; with 64 MB, PBDS may be too heavy.

12. No efficient split(). The PBDS tree class has a join() method, but it requires non-overlapping key ranges. There is no $O(\log n)$ split() as a treap or splay tree provides. For problems requiring frequent split/merge, use a treap or implicit treap instead.

Mental Traps

"This is just std::set with two extra methods."

Functionally, yes. But the extra methods have $O(\log n)$ cost, not $O(1)$. The implementation is an augmented BST that maintains subtree sizes at every node—not just at the root. Understanding how find_by_order walks the tree choosing left or right based on those subtree sizes helps you trust correctness and diagnose edge cases.

    How find_by_order(2) works internally:

         [30] size=5
         / \
      [10]  [40] size=2
      sz=2   / \
       \  [35] [50]
      [20] sz=1 sz=1
      sz=1

    Step 1: root [30], left_size=2, k=2
            left_size == k  -->  return this node (30)

    If k=3: left_size=2, k > left_size
            go right, k = 3 - 2 - 1 = 0
            at [40], left_size=1, k=0
            k < left_size --> go left --> return [35]

"order_of_key is a general binary search."

It isn't. order_of_key(x) counts elements less than $x$—it's a rank lookup, not a general predicate search. If you want the smallest element satisfying some condition, you need a different approach (e.g., walk with lower_bound or use find_by_order with a computed rank).

"PBDS is GCC-only, so it's not 'real' CP."

Codeforces, AtCoder, and most CP judges use GCC. Refusing to learn PBDS on principle means leaving an entire class of problems to contestants who happily write five lines of setup.

    Effort comparison:

    PBDS:     |#####|                      ~5 lines setup
    Fenwick:  |#####################|      ~30-40 lines + coord compress
    Seg Tree: |############################| ~50+ lines
              +---+---+---+---+---+---+---+
              0   5  10  15  20  25  30  35   lines of code

Spot the Bug

Bug 1—Duplicate insertion ignored:

ordered_set os;
os.insert(5);
os.insert(5);  // silently ignored -- size is still 1
cout << os.size(); // prints 1, not 2

Fix

Use ordered_multiset with pair<int,int>: os.insert({5, timer++}).

Bug 2—Dereferencing end():

ordered_set os;
os.insert(10);
cout << *os.find_by_order(1); // only 1 element, index 1 = end()

Fix

Always check if (k < os.size()) before dereferencing find_by_order(k).

Bug 3—Wrong inversion count with duplicates:

ordered_set os;
long long inv = 0;
for (int i = 0; i < n; i++) {
    inv += i - os.order_of_key(a[i]);  // BUG: counts elements < a[i], not <= a[i]
    os.insert(a[i]);                    // BUG: duplicates silently dropped
}

Fix

Use ordered_multiset. Count elements > a[i]: inv += i - oms.order_of_key({a[i]+1, 0}) and insert with oms.insert({a[i], timer++}).

Bug 4—Missing namespace:

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef tree<int, null_type, less<int>, rb_tree_tag,
             tree_order_statistics_node_update> ordered_set;

Fix

Add using namespace __gnu_pbds; or fully qualify: __gnu_pbds::tree<...>.

---

Comparison With Alternatives

The table below highlights when PBDS wins on simplicity and when a Fenwick tree or segment tree wins on raw performance.

Feature	PBDS ordered_set	Fenwick (BIT)	Segment tree	std::set
Insert / erase	$O(\log n)$	$O(\log C)$	$O(\log C)$	$O(\log n)$
$k$-th smallest	$O(\log n)$	$O({\log }^{2}C)$ or $O(\log C)$ via binary lifting	$O(\log C)$	$O(n)$
Count $<x$	$O(\log n)$	$O(\log C)$	$O(\log C)$	$O(n)$ or distance
Coordinate compression?	No	Yes	Yes	No
Code complexity	Low (~5 lines)	Medium (~30 lines)	High (~50 lines)	N/A
Works with arbitrary keys	Yes	Integers only	Integers only	Yes

$C$ = value range after compression.

Use PBDS when you need fast rank queries on a dynamic set and want minimal code. Use Fenwick when values are integers in a small range, or you need range-sum queries beyond rank operations.

    Effort comparison:

    PBDS:     |#####|                      ~5 lines setup
    Fenwick:  |#####################|      ~30-40 lines + coord compress
    Seg Tree: |############################| ~50+ lines
              +---+---+---+---+---+---+---+
              0   5  10  15  20  25  30  35   lines of code

Worked Problem: CF 1354D—Multiset

Problem (simplified): You have a multiset. Process $q$ operations:

• Type 1: add integer $x$.
• Type 2: remove the $k$-th smallest element.

After all operations, output any remaining element (or 0 if empty).

This is a direct application of ordered_multiset with find_by_order and erase.

#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;

typedef tree<
    pair<int, int>, null_type, less<pair<int, int>>,
    rb_tree_tag, tree_order_statistics_node_update
> ordered_multiset;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    ordered_multiset oms;
    int timer = 0;

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        oms.insert({x, timer++});
    }

    while (q--) {
        int type;
        cin >> type;
        if (type > 0) {
            oms.insert({type, timer++});
        } else {
            int k = -type; // 1-indexed
            auto it = oms.find_by_order(k - 1);
            oms.erase(it);
        }
    }

    if (oms.empty()) {
        cout << 0 << "\n";
    } else {
        cout << oms.find_by_order(0)->first << "\n";
    }
    return 0;
}

The actual CF 1354D input format differs slightly—adapt the parsing to match. The core logic is identical.

Can You...

Before moving on: write the typedef from memory. State what find_by_order(k) returns when k >= size(). Explain why order_of_key gives strictly less than, not ≤. Implement the pair<int,int> multiset trick. Derive the inversion formula. Explain why order_of_key(hi + 1) - order_of_key(lo) counts elements in [lo, hi].

Quick-Start Snippet

Five lines is all it takes to lift std::set into an order-statistic tree:

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,
             tree_order_statistics_node_update> ordered_set;

For duplicates, swap int for pair<value, unique_id>. For descending order, swap less with greater. Everything else—insert, erase, lower_bound, iteration—works exactly like std::set. When you see "$k$-th smallest" or "rank of element" in a problem with dynamic insertions and deletions, PBDS should be your first thought.

Practice Problems

#	Problem	Difficulty	Key Technique
1	CF 1354D - Multiset	CF 1600	ordered multiset, find_by_order, erase
2	CF 459D - Pashmak and Parmida's problem	CF 1800	inversions with PBDS or BIT
3	CF 61E - Enemy is Weak	CF 1600	inversion counting
4	CF 1042D - Petya and Array	CF 1800	prefix sums + order_of_key
5	CF 1311F - Moving Points	CF 1800	sorting + PBDS for prefix queries
6	SPOJ MKTHNUM - K-th Number	Medium	persistent seg tree or PBDS offline
7	CF 987C - Three displays	CF 1500	DP, but PBDS can help with extensions
8	CF 1284D - New Year and Conference	CF 2100	sweep + PBDS for interval queries
9	CSES - List Removals	Easy-Med	find_by_order + erase
10	CSES - Salary Queries	Medium	ordered set with range counting

Further Reading

Next Up: Union-Find (DSU)—another structure that manages dynamic sets, but for connectivity queries instead of order statistics.