The K-th One, Under Fire — Solution & Editorial

Back to the Problem

A Fenwick tree over the bits gives prefix-counts of ones; the k-th one is found by binary searching the prefix count (or by descending the Fenwick tree in O(log N)).

Complexity: O((N + Q) log N) (log² with plain binary search — also fine)