All problems
Offline Distinct Queries
Problem
Given nums and inclusive queries [left, right], return the number of distinct values inside each queried range, in the original query order.
Process queries sorted by right endpoint with a Fenwick tree that keeps a 1 only at the last seen position of each value: when a value reappears, remove its previous position and add the new one. A range sum then counts distinct values.
Hint
Keeping only the latest occurrence makes a prefix sum count each distinct value once.
Test cases
case 1
in: [[1,2,1,3],[[0,3],[1,2],[2,3]]]
expected: [3,2,2]
case 2
in: [[],[]]
expected: []
case 3
in: [[1,1,1],[[0,2]]]
expected: [1]
case 4
in: [[1,2,3],[[0,2],[1,1]]]
expected: [3,1]
case 5
in: [[5,5,5,5],[[0,3],[1,2]]]
expected: [1,1]
Starter codePython
def offline_distinct_queries(nums, queries):
# Your code here
pass5 test cases · run your code against them in the editor