there is no explanation by prateek bhaiya,how he arrived at the formula (ans[i]=ans[i-1]+i-prev occurence of a[i]).
i understood the working of the formula can you help me how bhaiya arrived at the formula after going through the problem statement. the formula is used by bhaiya at time 16:51 in the video.
Random query codeforces 846-B expectation
Understand it this way if you feel video wasn’t understandable.
For each index i we will find the number of pairs (l, r) (before swapping) such that i is the first occurence of ai in the chosen segment. Let f(i) be previous occurence of ai before i (if i is the first occurence, then f(i) = 0 if we suppose the array to be 1-indexed). Let’s find the number of pairs such that l ≤ r, and then multiply it by 2 and subtract 1 for this index. l has to be in segment (f(i), i], and r has to be in segment [i, n], so the number of ways to choose this pair is (i - f(i))(n - i + 1).
The value we receive as the sum of these values over all segments is the total number of distinct elements over all pairs (l, r), so we need to divide it by the number of these pairs.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.