P2C - Editorial

PROBLEM LINK:
Practice
Source

Author: SQU_Test

DIFFICULTY:
Medium

PREREQUISITES:
Dynamic Programming.

PROBLEM:
mar has an array a, consisting of n integers a_1, a_2, ..., a_n. The boy cannot sit and do nothing, he decided to study an array. Omar took a piece of paper and wrote out m integers l_1, l_2, ..., l_m (1 ≤ l_i ≤ n). For each number l_i he wants to know how many distinct numbers are staying on the positions l_i, l_i + 1, ..., n. Formally, he wants to find the number of distinct numbers among a_{l_i}, a_{l_i} + 1, ..., a_n.

Omar wrote out the necessary array elements but the array was so large and the boy was so pressed for time. Help him, find the answer for the described question for each l_i.

EXPLANATION:
We will count value ans_i — number of different elements on the suffix from i. For calculation will walk from the end of the array, and we count ans_i = ans_{i+1} + new_{a_i}, new_{a_i} equals to 1, if element a_i has not yet met and 0 otherwise. Or we can just add the elements to a set as we walk from the end of the array and we count ans_i as the size of the set.

TIME COMPLEXITY:
Time complexity of the solution is O(n + m).

SOLUTIONS:

Setter’s Solution
    n,m = map(int,input().split())
    a =  list(map(int,input().split()) )
    b = set()
    ans = [0] * n
    for i in range(n-1,-1,-1):
      b.add(a[i])
      ans[i] = len(b)

    for i in range(m):
      l = int(input())
      print(ans[l-1])