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_typeas Mapped makes it a set (a type instead gives an ordered map);rb_tree_tag= a red-black tree;tree_order_statistics_node_updatekeeps 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 instd::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
- What is an order statistics tree? A balanced BST whose nodes store subtree sizes, so rank and k-th queries take O(log n).
- Why is
distanceon astd::setslow? Set iterators are bidirectional, not random access, sodistancesteps one element at a time. - What does
order_of_key(x)return? The number of elements strictly less than x. - 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). - How do you store duplicates? As pairs (value, unique index), and query with sentinel pairs such as (x, −1) or (x, INT_MAX).
- What's the catch with
less_equal? It allows duplicates but breakserase,findandlower_boundsemantics. - 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+distanceis O(n). - g++'s
__gnu_pbdstree<…, tree_order_statistics_node_update>= ordered set:order_of_key,find_by_orderin O(log n). - Remember
using namespace __gnu_pbds;, 0-indexedfind_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