CODEFORCES: Sereja and Suffixes(368B)

Problem Link: http://codeforces.com/problemset/problem/368/B

Summary:
Given 'n' number of elements in array.

Given 'm' i.e 'm' different queries each query contains an integer 'l'.

Find the number of distinct elements from 'l' to 'n'  in array.

For Example:

input

10 10
1 2 3 4 1 2 3 4 100000 99999
1
2
3
4
5
6
7
8
9
10

output

6
6
6
6
6
5
4
3
2
1

Topic:
Dynamic Programming
Logic:

Let dp[i] be the answer i.e number of distinct elements from i to n.

and dp[i] = dp[i+1] +1 when element at a[i] has not been visited yet or visit[a[i]] = 0 otherwise dp[i] = dp[i+1] i.e visit[a[i]] = 1

For any 'l' print dp[l]  is the answer.

To View my solution:

https://github.com/shivam04/codes/blob/master/codeforces/seerja_and_suffixes.py