Distinct Values in Ranges

Difficulty: 2100 4000 ms 128 MB

fenwick offline

Answer Q queries: how many DISTINCT values occur in a_l..r?

Input: the first line has N and Q; the second line has the array; each of the next Q lines has l and r.

Output: one line per query with the distinct count.

Constraints:

• 1 ≤ N, Q ≤ 10⁵
• 1 ≤ a_i ≤ 10⁹

Sample Tests

5 3
1 2 1 3 2
1 3
2 5
3 3

2
3
1

1 1
7
1 1

1

Read the Editorial