Offline Distinct Range Queries (Sort by Right)

Problem

Count the distinct values in each inclusive range using offline queries and a Fenwick tree.

nums is the array and queries is a list of [l, r] pairs. Sort queries by right endpoint; sweep the array keeping only the most recent occurrence of each value in the BIT, so the range sum equals the number of distinct values. Answers are returned in the original query order.

Return the list of distinct counts.

Hint

Moving a value's 1 to its latest position makes a range sum count each value once.

Test cases

case 1

in: [[1,2,1,3],[[0,2],[1,3],[0,3]]]

expected: [2,3,3]

case 2

in: [[1,1,1],[[0,2]]]

expected: [1]

case 3

in: [[],[]]

expected: []

case 4

in: [[5,5,6],[[0,1],[1,2]]]

expected: [1,2]

Starter codePython

def distinct_range_queries(nums, queries):
    # Your code here
    pass

4 test cases · run your code against them in the editor