CT080

The Archive of Versioned Crystals

HardL8 · Quantum CoderAcceptance: 0.0%XP: 250

Curator Sona freezes a new sorted-value snapshot after each crystal is added. For every historical range, answer its k-th smallest crystal without rebuilding the archive. Input: n q; n values; q triples l r k (1-based inclusive range and rank). Output the k-th smallest value in each range.

Example 1:

Input: 5 3 5 1 4 2 3 1 5 3 2 4 1 2 5 4
Output: 3 1 4

Example 2:

Input: 4 1 -1 -1 8 0 1 4 2
Output: -1

Example 3:

Input: 1 1 7 1 1 1
Output: 7

Constraints:

1≤n,q≤200000; |value|≤10^9; 1≤k≤r-l+1.

Tags:

persistent-segment-tree order-statistics
Loading...
Test Cases:No test cases
No test cases available.