for those who came to this problem through cp-algorithms fenwick tree/BIT page and want hints to solve this problem using BIT:

imagine you have distinct array and ask the same thing that you have to answer how many distinct element there in a range. it is easy right! you would only have to create a BIT array of size n with all 1 in it and answer the queries.

same way how can you make the given array distinct?? you will have to create an BIT array for the given array without duplicates. for example:
array-> 1 1 2 1 3
bit array -> 1 0 1 0 1

as you can see i only consider the leftmost element of every duplicate element. as a result for avobe bit array i can only answer query which left range start at 0. meaning now i have a restriction on in which order i should answer the queries. so a offline problem. :)

The problem can be reduced to KQUERYO (but instead of elements strictly greater than k like in KQUERYO, you want to find elements strictly less than k) by making new array prev where prev[i] represents the previous index arr[i] occurred at. In the case where it's the first occurrence of arr[i] in the array, you can denote prev[i] with a negative number. Then, it becomes a problem of finding the number of elements in [l, r] such that prev[i] < l, or in other words, you want to count only the first occurrence of each number in [l, r]—If prev[i] > l, then another occurence of it must exist in [l, r], meaning it's a duplicate that shouldn't be counted. This sort of problem is straightforward to solve using a wavelet tree or persistent segment tree.

Alternatively, you can also use Mo's algorithm to solve the queries offline.

KQUERYO: https://www.spoj.com/problems/KQUERYO/

Using map gives TLE but using a vector of frequencies gives AC.

simple MO algorithm

莫队和树没有关系吧（雾