Problem Description You are given an integer array arr of length n. A subarray arr[i] is considered good if it contains at least one integer that appears exactly once within the subarray. You can select any element in arr[] and replace it with any integer. Find the minimum number of elements needed to be replaced so that every subarray of the array becomes good.
Examples
Example 1: Input: n = 4, arr = [1, 2, 1, 2] Output: 1 Explanation: Replace 0th element (0-based indexing) with 3 to get [3, 2, 1, 2]. Now, every subarray contains at least one element that appears exactly once within it. Thus, the answer is 1.
Example 2: Input: n = 4, arr = [4, 4, 4, 4] Output: 2 Explanation: Replace 0th and 2nd element (0-based indexing) with 3 and 5 respectively to get [3, 4, 5, 4]. Now, every subarray contains at least one element that appears exactly once within it. Thus, the answer is 2.
Example 3: Input: n = 5, arr = [1, 3, 2, 1, 2] Output: 0 Explanation: Every subarray already contains at least one element that appears exactly once in it. Thus, the answer is 0.
Constraints
1 <= n <= 2 * 10^5
1 <= arr[i] <= n
Did you find the solution?
This is same as this 1969E, you can check its editorial.
When we do an operation on index i, we can set arr[i] to be any number that doesn't occur in arr. By doing so, any subarray [l,r], l <= i <= r will become good and any other subarray will not be affected. Therefore, for a fixed i it is an optimal operation. Let's call a subarray perfect if all of its subarrays are good. We can note that our answer is the minimal k, such that there exists S = {i1,i2...ik} s.t. subarrays [1,i1), (i1,i2)...(ik,n] are perfect. Note that if a subarray [l,r] is perfect, subarray [l,r-1] would also be perfect, therefore, for a fixed l we can find maximal r s.t. [l,r] is perfect. We can greedily erase the longest perfect prefix and calculate the number of such operations.
[3,3,4,4,5]=>(0,4) is perfect but not (0,3) so if (l,r) is perfect then (l,r-1) will also be perfect doesn't hold good
[3,3,4,4] is not perfect, since its subarrays [4,4] and [3,3] aren't good.
ohhh u meant all the subarrays in [l,r], my bad
yes, but i hope you realized tracking the longest perfect prefix isn't straightforward.
Let's assume [1,r] is perfect, since [1,r] is perfect, [1,r+1] is perfect iff subarrays [1,r+1], [2,r+1], ..., [r+1,r+1] are good. To check this condition, we can maintain array V, such that V[i] = # of unique elements in range [i,r+1] and check if min(V[1],V[2],...V[r+1]) > 0. In transition from r to r+1, a[r+1] will stop adding 1 to V on range [prv[prv[r+1]]+1,prv[r+1]] and starts adding 1 on range [prv[r+1]+1,r+1], where prv[i] = maximal j < i, s.t. a[i] = a[j]. Therefore, we can do += operation on range and get min on an interval of V, which is doable with segment tree with lazy propagation.
orz, thanks a lot understood in one go!.
Go from right to left if for an index i there is a sub array starting from i with no element with single occurrence then replace i with an element that is not present in array and do ans++, return ans(checking at an index i can be done using seg tree)
checking at an index was the part i wasn't able to do :( i'll try and understand it from the editorial of this 1969E
Is this the same problem as https://codeforces.me/problemset/problem/1969/E?
oh yeah it is! thanks a lot.