Distinct Values in a Range
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
Given an integer array a and a list of queries, answer each query queries[k] = [l, r] with the number of distinct
values among a[l], a[l+1], ..., a[r] (0-based, both ends inclusive). Return the answers in query order.
Examples
| a | queries | result |
|---|---|---|
[1, 2, 1, 3, 2] | [[0, 4], [0, 2], [1, 1], [2, 3]] | [3, 2, 1, 2] |
[7, 7, 7] | [[0, 2], [1, 2]] | [1, 1] |
Example 1 — [1, 2, 1, 3, 2] holds 1, 2, 3; [1, 2, 1] holds two values; a single element is one value; [1, 3] is two.
Example 2 — every value is the same, so each answer is 1.
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
-
a.length -
a[i] -
queries.length queries[k] = [l, r],
Expected complexity
- Time
- O((N + Q) log N)
- Space
- O(N + Q)
Examples
| a | queries | Expected |
|---|---|---|
[1,2,1,3,2] | [[0,4],[0,2],[1,1],[2,3]] | [3,2,1,2] |
[7,7,7] | [[0,2],[1,2]] | [1,1] |
Hint
Hint
Process the queries offline, sorted by right end r. While sweeping r, keep a 1 only at the last position where each
value has appeared (move it when the value reappears); the answer to [l, r] is then the sum over positions l..r, which a
Fenwick tree gives in . Mo's algorithm () also works. Scanning each range is and exceeds the
time limit.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 286 ms | estimated |
| C++ (GCC, gnu++23) | 286 ms | derived |
| Python 3.13 | 1304 ms | derived |
| Java 25 | 2482 ms | derived |
| Kotlin 2.4 (JVM) | 1572 ms | estimated |
| C# 14 (.NET 10) | 1572 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 2 | inputs and outputs |
| correctness | 40 | 11 | verdict only |
| performance | 60 | 4 | verdict only |