Module 16 · The STL in Competitive Programming: Which Container for Which Problem
Changing Ranks With GCC pb_ds, and What a Plain Set Cannot Promise
ProReading
Maria keeps adding and removing labels from a live shelf. Now she asks for the fifth smallest label and how many labels are below a threshold. A set knows sorted order. That sounds enough, until walking to each answer becomes the expensive part.
Checking what this lesson needs for you…
What is inside Changing Ranks With GCC pb_ds, and What a Plain Set Cannot Promise
- This is a GCC extension
- Read the typedef one choice at a time
- Select a zero-based rank
- Count strict predecessors
- Updates change ranks, not identities
- Subtree sizes make rank queries possible
- Keep duplicates with unique ids
- Compare the same query across three choices
- Run the rank-query lab
- Decide whether the extension earns its place