Skip to main content

Slots: kth Empty and Range Count

Challenge on lesson: Checkpoint — Fenwick Mastery

CHALLENGE
Difficulty: advanced+25 XP

**Bài toán.** n empty slots in a row, q operations: 1 k — occupy the k-th still-empty slot and print its 1-based position; 2 l r — print the number of occupied slots in [l, r]. **Constraints:** 1 ≤ n, q ≤ 200 000; for op 1, k never exceeds the number of empty slots. One Fenwick serves both jobs: descent on empty counts for op 1 (block empties = len − occupied), prefix difference for op 2.

Back to lesson: Checkpoint — Fenwick Mastery