Funcia
Lv.4coordinate-compressionpersistent-segment-treesegment-tree

K-th Smallest in a Range

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

Given an integer array a (which never changes) and queries, answer each query [l, r, k] with the k-th smallest value of a[l..r] (0-based, both ends inclusive, k counted from 1; equal values are counted separately). Return the answers in query order.

Examples

aqueriesresult
[5, 1, 4, 2, 3][[0, 4, 2], [1, 3, 3], [2, 2, 1], [0, 2, 3]][2, 4, 4, 5]
[2, 2, 1, 2][[0, 3, 1], [0, 3, 2], [1, 2, 2]][1, 2, 2]

Example 1 — the whole array sorted is [1, 2, 3, 4, 5]; [1, 4, 2] sorted is [1, 2, 4]; and so on.

Example 2 — duplicates count separately: [1, 2, 2, 2].

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(a: int[], queries: int[][]) → int[]

Constraints

  • 1≤N=1 \le N = a.length ≤100,000\le 100{,}000
  • −109≤-10^9 \le a[i] ≤109\le 10^9
  • 1≤1 \le queries.length ≤100,000\le 100{,}000
  • queries[q] = [l, r, k], 0≤l≤r<N0 \le l \le r < N, 1≤k≤r−l+11 \le k \le r - l + 1

Expected complexity

Time
O((N + Q) log N)
Space
O(N log N)

Examples

aqueriesExpected
[5,1,4,2,3][[0,4,2],[1,3,3],[2,2,1],[0,2,3]][2,4,4,5]
[2,2,1,2][[0,3,1],[0,3,2],[1,2,2]][1,2,2]

Hint

Hint

Compress values to ranks and think of a segment tree that counts how many elements have each rank; walking down ("go left if the left count is at least k, otherwise subtract and go right") finds the k-th value in O(log⁡N)O(\log N). Keep one such tree per prefix a[0..i-1] as a persistent segment tree (each version copies only one root-to-leaf path), and walk T_{r+1} - T_l for the range. A merge sort tree or wavelet tree also works. Per-query selection is O(NQ)O(NQ) and exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)318 msestimated
C++ (GCC, gnu++23)318 msderived
Python 3.132576 msderived
Java 252126 msderived
Kotlin 2.4 (JVM)1636 msestimated
C# 14 (.NET 10)1636 msestimated

Test groups

GroupWeightTestsVisibility
sample02inputs and outputs
correctness4010verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.