SyntaxPilot
Courses/Competitive Programming/Lesson 68
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Competitive Programming · Lesson 68 of 90

Ordered set (policy-based data structures)

queued

These are the notes for Competitive Programming episode 68. A std::set keeps values sorted but can't say quickly how many values are smaller than x (the rank) or which value is k-th: distance(s.begin(), it) walks the set one element at a time, O(n). A balanced search tree that stores subtree sizes (an order statistics tree) answers both in O(log n), and g++ ships one in its policy-based data structures (__gnu_pbds): tree<…, tree_order_statistics_node_update>, used as an ordered set with order_of_key(x) and find_by_order(k). Live Leaderboard (how many earlier scores are lower, after each new score) shows a sorted vector (TLE: insert shifts), std::set + distance (TLE), the compile error without the namespace, equal scores vanishing from a set (3 instead of 4), and the fix with (score, index) pairs. Ticket Circle (every k-th person in a circle leaves) uses find_by_order + erase. Stress tests pass. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.

The real-life hook

A huge filing cabinet keeps files in sorted order. Counting files from the first one to find the 500th is what distance does. A better office writes on every drawer and folder label how many files are inside, and updates the labels on the way whenever a file goes in or out. Now the 500th file: drawer 1 has 300 files, so skip it; drawer 2 has 250, so it's the 200th file of drawer 2; open it and repeat with its folders. A few steps instead of 500. Those labels are subtree sizes.

Problem R1 · Live Leaderboard

(Written for this course.)

  • Input: n (n ≤ 10^6), then n scores (≤ 10^9, equal scores allowed), in the order they arrive.
  • After each score x: print how many earlier scores are strictly lower than x.
6
50 20 70 50 90 20

Answers: 0, 0, 2, 1, 4, 0 (90 beats 50, 20, 70 and the second 50).

Attempt 1: a sorted vector (TLE)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<int> v;                                  // all scores so far, sorted

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        auto it = lower_bound(v.begin(), v.end(), x);
        int lower = it - v.begin();       // scores below x
        v.insert(it, x);                         // shifts everything after it
        cout << lower << "\n";
    }
}
0
0
2
1
4
0

A million scores:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<int> v;

int main() {
    int n = 1000000;                              // a million scores
    mt19937 rng(68);
    ll check = 0;
    for (int i = 0; i < n; i++) {
        int x = rng() % 1000000000;
        auto it = lower_bound(v.begin(), v.end(), x);
        int lower = it - v.begin();       // scores below x
        v.insert(it, x);                         // shifts everything after it
        check += lower;
    }
    cout << check << "\n";
}
Time Limit Exceeded

lower_bound is O(log n), but insert shifts every later element: O(n) per score.

Attempt 2: std::set + distance (TLE, and duplicates vanish)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

set<int> s;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        s.insert(x);
        int lower = distance(s.begin(), s.lower_bound(x));   // walks the set!
        cout << lower << "\n";
    }
}
0
0
2
1
3
0

Note the 3 for 90: a set stores one copy of 50.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

set<int> s;

int main() {
    int n = 1000000;                              // a million scores
    mt19937 rng(68);
    ll check = 0;
    for (int i = 0; i < n; i++) {
        int x = rng() % 1000000000;
        s.insert(x);
        int lower = distance(s.begin(), s.lower_bound(x));   // walks the set!
        check += lower;
    }
    cout << check << "\n";
}
Time Limit Exceeded

std::set iterators are bidirectional, so distance steps through every element: O(n), hidden in one call.

Subtree sizes

In a balanced binary search tree, let every node store the size of its subtree. To count values below x, walk from the root: when x is bigger than the node's value, everything in the node's left subtree and the node itself are below x, so add size(left) + 1 and go right; otherwise go left. For the keys 20 40 50 60 70 90 95 and x = 75: at 60 add 3 + 1, at 90 go left, at 70 add 1 → 5. One root-to-leaf path: O(log n). Finding the k-th value walks down the same way, comparing k with the left subtree's size.

The ordered set in g++

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag,
                         tree_order_statistics_node_update>;
  • tree<Key, Mapped, Compare, Tag, NodeUpdate>: null_type as Mapped makes it a set (a type instead gives an ordered map); rb_tree_tag = a red-black tree; tree_order_statistics_node_update keeps the subtree sizes.
  • os.order_of_key(x): the number of elements strictly less than x.
  • os.find_by_order(k): an iterator to the k-th element, counting from 0 (end() if k ≥ size).
  • insert, erase (by value or iterator), find, lower_bound, upper_bound, size: as in std::set, all O(log n).

The compile error without the namespace

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag,
                         tree_order_statistics_node_update>;
using ll = long long;

ordered_set os;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        int lower = os.order_of_key(x);          // how many are < x
        os.insert(x);
        cout << lower << "\n";
    }
}
main.cpp:5:21: error: ‘tree’ does not name a type
    5 | using ordered_set = tree<int, null_type, less<int>, rb_tree_tag,
      |                     ^~~~
main.cpp:9:1: error: ‘ordered_set’ does not name a type
    9 | ordered_set os;
      | ^~~~~~~~~~~
main.cpp: In function ‘int main()’:
main.cpp:19:21: error: ‘os’ was not declared in this scope; did you mean ‘cos’?
   19 |         int lower = os.order_of_key(x);          // how many are < x
      |                     ^~
      |                     cos

With the namespace: fast, but duplicates still vanish

#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;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag,
                         tree_order_statistics_node_update>;
using ll = long long;

ordered_set os;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        int lower = os.order_of_key(x);          // how many are < x
        os.insert(x);
        cout << lower << "\n";
    }
}
0
0
2
1
3
0

The fix: (score, index) pairs

Indexes are all different, so equal scores stay apart. The pair (x, −1) is smaller than every (x, i) with i ≥ 0, so order_of_key({x, -1}) counts exactly the scores below x.

#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;
using ordered_set = tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag,
                         tree_order_statistics_node_update>;
using ll = long long;

ordered_set os;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        int lower = os.order_of_key({x, -1});    // pairs below (x, −1)
        os.insert({x, i});                       // the index keeps equal scores apart
        cout << lower << "\n";
    }
}
0
0
2
1
4
0

A million scores (about a second; the sum of the answers as a check number):

#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;
using ordered_set = tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag,
                         tree_order_statistics_node_update>;
using ll = long long;

ordered_set os;

int main() {
    int n = 1000000;                              // a million scores
    mt19937 rng(68);
    ll check = 0;
    for (int i = 0; i < n; i++) {
        int x = rng() % 1000000000;
        int lower = os.order_of_key({x, -1});    // pairs below (x, −1)
        os.insert({x, i});                       // the index keeps equal scores apart
        check += lower;
    }
    cout << check << "\n";
}
249567119251

Stress test (scores 0..9: many ties)

#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;
using ordered_set = tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag,
                         tree_order_statistics_node_update>;
using ll = long long;

int main() {
    mt19937 rng(68);
    for (int t = 1; t <= 500; t++) {
        ordered_set os;
        vector<int> seen;
        int n = rng() % 50 + 1;
        for (int i = 0; i < n; i++) {
            int x = rng() % 10;                  // lots of equal scores
            int slow = count_if(seen.begin(), seen.end(), [&](int y) { return y < x; });
            if ((int)os.order_of_key({x, -1}) != slow) { cout << "mismatch on test " << t; return 0; }
            os.insert({x, i}), seen.push_back(x);
        }
    }
    cout << "all 500 tests passed";
}
all 500 tests passed

Problem R2 · Ticket Circle

(Written for this course, in the style of the classic Josephus problem.)

  • Input: n k (n ≤ 10^6, k ≤ 10^9). n people stand in a circle, numbered 1..n. Starting from person 1, count k people; the k-th gets a ticket and leaves; counting continues from the next person.
  • Output: the order in which they leave.
7 3

Answer: 3 6 2 7 5 1 4.

Observation. Keep the waiting people in order and let pos be the 0-based index to count from. The k-th is at (pos + k − 1) mod size; after he leaves, the next person slides into that same index. So each step needs "the pos-th remaining person" and "erase him": find_by_order and erase.

The obvious attempt: vector erase (TLE)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<int> circle(n);
    iota(circle.begin(), circle.end(), 1);        // people 1..n
    int pos = 0;
    while (!circle.empty()) {
        pos = (pos + k - 1) % circle.size();     // the k-th from here
        cout << circle[pos] << " ";
        circle.erase(circle.begin() + pos);       // shifts the rest
    }
}
3 6 2 7 5 1 4 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n = 1000000, k = 1000;                    // a million people
    ll check = 0, step = 0;
    vector<int> circle(n);
    iota(circle.begin(), circle.end(), 1);        // people 1..n
    int pos = 0;
    while (!circle.empty()) {
        pos = (pos + k - 1) % circle.size();     // the k-th from here
        check += ++step * circle[pos];
        circle.erase(circle.begin() + pos);
    }
    cout << check << "\n";
}
Time Limit Exceeded

find_by_order + 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;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag,
                         tree_order_statistics_node_update>;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    ordered_set people;
    for (int i = 1; i <= n; i++) people.insert(i);
    int pos = 0;
    while (!people.empty()) {
        pos = (pos + k - 1) % people.size();
        auto it = people.find_by_order(pos);       // the pos-th person, 0-indexed
        cout << *it << " ";
        people.erase(it);
    }
}
3 6 2 7 5 1 4 
1 5
1 

A million people, k = 1000 (Σ step · person as a check number):

#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;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag,
                         tree_order_statistics_node_update>;
using ll = long long;

int main() {
    int n = 1000000, k = 1000;                    // a million people
    ll check = 0, step = 0;
    ordered_set people;
    for (int i = 1; i <= n; i++) people.insert(i);
    int pos = 0;
    while (!people.empty()) {
        pos = (pos + k - 1) % people.size();
        auto it = people.find_by_order(pos);       // the pos-th person, 0-indexed
        check += ++step * *it;
        people.erase(it);
    }
    cout << check << "\n";
}
250035768789876423

Stress test (against the vector)

#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;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag,
                         tree_order_statistics_node_update>;
using ll = long long;

int main() {
    mt19937 rng(68);
    for (int t = 1; t <= 500; t++) {
        int n = rng() % 40 + 1, k = rng() % 60 + 1;
        ordered_set people;
        vector<int> circle;
        for (int i = 1; i <= n; i++) people.insert(i), circle.push_back(i);
        int p = 0, q = 0;
        while (!circle.empty()) {
            p = (p + k - 1) % people.size(), q = (q + k - 1) % circle.size();
            auto it = people.find_by_order(p);
            if (*it != circle[q]) { cout << "mismatch on test " << t; return 0; }
            people.erase(it), circle.erase(circle.begin() + q);
        }
    }
    cout << "all 500 tests passed";
}
all 500 tests passed

Complexity vs the constraints

Method Insert / erase Rank / k-th Verdict (n = 10^6)
sorted vector O(n) O(log n) TLE
std::set + distance O(log n) O(n) TLE
ordered set (__gnu_pbds) O(log n) O(log n) accepted (~1 s)
R2: vector erase O(n) O(1) TLE
R2: find_by_order + erase O(log n) O(log n) accepted

The ordered set's constant factor is a few times bigger than std::set's, and it uses more memory per element; use it only when ranks or k-th elements are needed. Without g++ (Java, Python, MSVC), a Fenwick tree over compressed values does the same job (see the Java and Python solutions below, and episode 63).

Common mistakes (and the real outputs)

Mistake What you see Why Fix
no using namespace __gnu_pbds; error: ‘tree’ does not name a type tree lives in that namespace add the using line
duplicates in tree<int, …> 3 (expected 4) a set keeps one copy pair<value, index>
less_equal<int> as a "multiset" erase / find misbehave equal keys never compare equal pairs instead
find_by_order counted from 1 off-by-one answers it's 0-indexed find_by_order(k − 1) for the k-th
distance on set iterators Time Limit Exceeded walks one by one order_of_key
*find_by_order(k) with k ≥ size Runtime Error returns end() check k < size()
sorted vector insert Time Limit Exceeded shifts the tail ordered set

Mini project

Write an OrderedMultiset wrapper around tree<pair<T, int>, …> with insert(x), eraseOne(x), countLess(x), countLessEqual(x) and kth(k) (1-based). Test it against a sorted std::vector on random operations, including erasing values that aren't present.

Practice

These are the homework problems from the episode. The C++ solutions were checked against a brute force on 300 random tests.

1. Count inversions (pairs i < j with a[i] > a[j]).

Solution

Before inserting a[i], the earlier values strictly bigger than it are i − order_of_key({a[i], INT_MAX}).

#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;
using ordered_set = tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag,
                         tree_order_statistics_node_update>;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    ordered_set seen;
    ll inversions = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        inversions += i - seen.order_of_key({x, INT_MAX});   // earlier values strictly bigger than x
        seen.insert({x, i});
    }
    cout << inversions << "\n";
}

On the leaderboard sample:

6

2. Running median of a stream (after each value, print the lower median).

Solution

After i + 1 values, the lower median is find_by_order(i / 2).

#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;
using ordered_set = tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag,
                         tree_order_statistics_node_update>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    ordered_set s;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        s.insert({x, i});
        cout << s.find_by_order(i / 2)->first << (i + 1 < n ? " " : "\n");   // the lower median
    }
}

On the leaderboard sample:

50 20 50 50 50 50

3. Count pairs i < j with |a[i] − a[j]| ≤ d.

Solution

For each new value x, add order_of_key({x + d, INT_MAX}) − order_of_key({x − d, -1}) (the earlier values in [x − d, x + d]), then insert {x, i}. Use long long for the total.

4. The k-th smallest in every sliding window of length w.

Solution

Insert {a[i], i}; once i ≥ w, erase {a[i − w], i − w}; when the window is full, print find_by_order(k − 1)->first. O(n log n).

Quick quiz

os = {10, 20, 30, 40, 50}
cout << os.order_of_key(35) << " " << *os.find_by_order(1);

A) 3 20 · B) 3 10 · C) 4 20 · D) 2 30

Answer

A. Three values are below 35 (10, 20, 30). find_by_order counts from 0, so index 1 is 20.

Interview questions

  1. What is an order statistics tree? A balanced BST whose nodes store subtree sizes, so rank and k-th queries take O(log n).
  2. Why is distance on a std::set slow? Set iterators are bidirectional, not random access, so distance steps one element at a time.
  3. What does order_of_key(x) return? The number of elements strictly less than x.
  4. What does find_by_order(k) return? An iterator to the element at 0-based position k in sorted order (end() if out of range).
  5. How do you store duplicates? As pairs (value, unique index), and query with sentinel pairs such as (x, −1) or (x, INT_MAX).
  6. What's the catch with less_equal? It allows duplicates but breaks erase, find and lower_bound semantics.
  7. What if pbds isn't available? A Fenwick tree over compressed values (offline), or a treap / segment tree.

Glossary

Term Meaning Example
Rank of x How many values are smaller than x 90 beats 4 scores
k-th element The value at position k in sorted order find_by_order(1) = 20
Order statistics tree A balanced BST with subtree sizes the drawer labels
Subtree size How many nodes are in a node's subtree 60 · size 7
Balanced BST A search tree with O(log n) height red-black tree
Red-black tree The balanced BST behind std::set and rb_tree_tag rb_tree_tag
Policy-based data structures g++ extension library __gnu_pbds tree<…>
null_type "No mapped value": makes tree a set ordered set
tree_order_statistics_node_update The policy that keeps subtree sizes enables the two calls
order_of_key(x) Number of elements < x order_of_key(35) = 3
find_by_order(k) Iterator to the k-th element, from 0 *find_by_order(0) = smallest
distance Steps between two iterators (O(n) for a set) the hidden TLE
Bidirectional iterator Moves one step at a time, both ways set iterators
Sentinel pair A pair chosen to sit just below / above all pairs with a value {x, -1}
Josephus problem Every k-th person in a circle leaves the ticket circle
Fenwick tree A prefix-sum tree; also does rank / k-th on compressed values Java / Python solutions
Stress test Comparing a fast solution with a slow, surely-correct one on many random inputs all 500 tests passed
Compilation Error The program doesn't compile ‘tree’ does not name a type
Treap A randomized balanced BST with split and merge next episode

Summary

  • Rank and k-th need subtree sizes; std::set + distance is O(n).
  • g++'s __gnu_pbds tree<…, tree_order_statistics_node_update> = ordered set: order_of_key, find_by_order in O(log n).
  • Remember using namespace __gnu_pbds;, 0-indexed find_by_order, and (value, index) pairs for duplicates.
  • k-th remaining + erase solves the ticket circle in O(n log n).

Solutions in C++, Java and Python

Problem R1 · Live Leaderboard

C++

#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;
using ordered_set = tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag,
                         tree_order_statistics_node_update>;
using ll = long long;

ordered_set os;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        int lower = os.order_of_key({x, -1});    // pairs below (x, −1)
        os.insert({x, i});                       // the index keeps equal scores apart
        cout << lower << "\n";
    }
}
0
0
2
1
4
0

Java (no ordered set in Java: a Fenwick tree over sorted scores)

import java.util.*;
import java.io.*;

// Java has no ordered set with ranks; a Fenwick tree over compressed scores does the same job here.
public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedInputStream(System.in));
        in.nextToken(); int n = (int) in.nval;
        int[] x = new int[n];
        for (int i = 0; i < n; i++) { in.nextToken(); x[i] = (int) in.nval; }
        int[] vals = x.clone();
        Arrays.sort(vals);
        int[] bit = new int[n + 1];                         // bit over ranks 1..n
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            int r = lowerBound(vals, x[i]);                 // scores below x have ranks 1..r
            int lower = 0;
            for (int j = r; j > 0; j -= j & -j) lower += bit[j];
            sb.append(lower).append('\n');
            for (int j = r + 1; j <= n; j += j & -j) bit[j]++;   // insert x at rank r + 1
        }
        System.out.print(sb);
    }
    static int lowerBound(int[] v, int k) {
        int lo = 0, hi = v.length;
        while (lo < hi) { int mid = (lo + hi) >>> 1; if (v[mid] < k) lo = mid + 1; else hi = mid; }
        return lo;
    }
}
0
0
2
1
4
0

Python (the same Fenwick idea)

import sys
from bisect import bisect_left

# Python has no ordered set with ranks; a Fenwick tree over compressed scores does the same job here.
def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    x = [int(v) for v in data[1:n + 1]]
    vals = sorted(x)
    bit = [0] * (n + 1)
    out = []
    for v in x:
        r = bisect_left(vals, v)                 # scores below v have ranks 1..r
        lower, j = 0, r
        while j > 0:
            lower += bit[j]; j -= j & -j
        out.append(lower)
        j = r + 1                                # insert v at rank r + 1
        while j <= n:
            bit[j] += 1; j += j & -j
    print("\n".join(map(str, out)))

main()
0
0
2
1
4
0

Problem R2 · Ticket Circle

C++

#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;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag,
                         tree_order_statistics_node_update>;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    ordered_set people;
    for (int i = 1; i <= n; i++) people.insert(i);
    int pos = 0;
    while (!people.empty()) {
        pos = (pos + k - 1) % people.size();
        auto it = people.find_by_order(pos);       // the pos-th person, 0-indexed
        cout << *it << " ";
        people.erase(it);
    }
}
3 6 2 7 5 1 4 

Java (Fenwick tree of ones + binary lifting for the k-th remaining person)

import java.util.*;
import java.io.*;

// The ticket circle with a Fenwick tree: bit holds 1 for every person still waiting,
// and "the pos-th remaining person" is found by binary lifting over the tree.
public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedInputStream(System.in));
        in.nextToken(); int n = (int) in.nval; in.nextToken(); long k = (long) in.nval;
        int[] bit = new int[n + 1];
        for (int i = 1; i <= n; i++) { bit[i]++; int j = i + (i & -i); if (j <= n) bit[j] += bit[i]; }   // all ones, O(n)
        int LOG = 1; while ((1 << LOG) <= n) LOG++;
        StringBuilder sb = new StringBuilder();
        int size = n, pos = 0;
        while (size > 0) {
            pos = (int) ((pos + k - 1) % size);
            int idx = 0, rem = pos + 1;                       // find the (pos + 1)-th one
            for (int b = LOG; b >= 0; b--) {
                int nx = idx + (1 << b);
                if (nx <= n && bit[nx] < rem) { idx = nx; rem -= bit[nx]; }
            }
            int person = idx + 1;
            sb.append(person).append(' ');
            for (int j = person; j <= n; j += j & -j) bit[j]--;
            size--;
        }
        System.out.println(sb.toString().trim());
    }
}
3 6 2 7 5 1 4

Python

import sys

# The ticket circle with a Fenwick tree: bit holds 1 for every person still waiting.
def main():
    n, k = map(int, sys.stdin.read().split())
    bit = [0] * (n + 1)
    for i in range(1, n + 1):                    # all ones, O(n)
        bit[i] += 1
        j = i + (i & -i)
        if j <= n: bit[j] += bit[i]
    LOG = n.bit_length()
    out, size, pos = [], n, 0
    while size:
        pos = (pos + k - 1) % size
        idx, rem = 0, pos + 1                    # find the (pos + 1)-th remaining person
        for b in range(LOG, -1, -1):
            nx = idx + (1 << b)
            if nx <= n and bit[nx] < rem:
                idx = nx; rem -= bit[nx]
        person = idx + 1
        out.append(person)
        j = person
        while j <= n:
            bit[j] -= 1; j += j & -j
        size -= 1
    print(" ".join(map(str, out)))

main()
3 6 2 7 5 1 4