Funcia
Lv.4fenwick-treemo-algorithmoffline-queries

Distinct Values in a Range

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
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

aqueriesresult
[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

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

Expected complexity

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

Examples

aqueriesExpected
[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 O(log⁡N)O(\log N). Mo's algorithm (O((N+Q)N)O((N+Q)\sqrt{N})) also works. Scanning each range is O(NQ)O(NQ) and exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)286 msestimated
C++ (GCC, gnu++23)286 msderived
Python 3.131304 msderived
Java 252482 msderived
Kotlin 2.4 (JVM)1572 msestimated
C# 14 (.NET 10)1572 msestimated

Test groups

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

No result yet. Run or submit your code.