Editorial for Another Contest 3 Problem 1 - Diverse Arrays
Submitting an official solution before solving the problem yourself is a bannable offence.
If an array is not diverse, it has fewer than distinct elements present.
There are subarrays, so we can enumerate the arrays which are not diverse and then the remaining ones must be diverse.
Lemma: Let be the leftmost index such that the subarray from to is not diverse. If , then .
Proof: By contradiction - if but , then we could extend to be at least as small as since that subarray would be a subarray of the array defined by and .
Therefore, if we loop from left to right and maintain in amortized constant time, we can enumerate all the arrays which are not diverse. To do this, we advance by one and maintain a frequency map of numbers to how many times we observe them. If the frequency map is at least in size, we remove the leftmost element still present in the subarray and repeat this until the frequency map has size less than . The size of the remaining subarray is the number of subarrays ending at that index which are not diverse.