Paint the Middle
Contest: Codeforces Round 768 (Div. 1)
Difficulty rating: 2200
Tags: dp, greedy, sortings, two pointers

You are given $$$n$$$ elements numbered from $$$1$$$ to $$$n$$$, the element $$$i$$$ has value $$$a_i$$$ and color $$$c_i$$$, initially, $$$c_i = 0$$$ for all $$$i$$$.

The following operation can be applied:

- Select three elements $$$i$$$, $$$j$$$ and $$$k$$$ ($$$1 \leq i < j < k \leq n$$$), such that $$$c_i$$$, $$$c_j$$$ and $$$c_k$$$ are all equal to $$$0$$$ and $$$a_i = a_k$$$, then set $$$c_j = 1$$$.

Find the maximum value of $$$\sum\limits_{i=1}^n{c_i}$$$ that can be obtained after applying the given operation any number of times.

Input format:
The first line contains an integer $$$n$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$) — the number of elements.

The second line consists of $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq n$$$), where $$$a_i$$$ is the value of the $$$i$$$-th element.

Output format:
Print a single integer in a line — the maximum value of $$$\sum\limits_{i=1}^n{c_i}$$$ that can be obtained after applying the given operation any number of times.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test, it is possible to apply the following operations in order:

Example input:
7
1 2 1 2 7 4 7

Example output:
2

Example input:
13
1 2 3 2 1 3 3 4 5 5 5 4 7

Example output:
7

Editorial:
For each $$$x$$$ such that all the elements $$$a_1, a_2, ..., a_x$$$ are different from $$$a_{x+1}, a_{x+2}, ..., a_n$$$ it is impossible to apply an operation with some indices from the first part, and some other from the second one.
Then it is possible to split the array in subarrays for each $$$x$$$ such that the previous condition holds, and sum the answers from all of them.
Let's solve the problem independently for one of those subarrays, let's denote its length as $$$m$$$, the values of its elements as $$$a_1, ..., a_m$$$ and their colors as $$$c_1, ..., c_m$$$:
For every tuple $$$(x, y, z)$$$ such that $$$1 \le x < y < z \le m$$$ and $$$a_x = a_y = a_z$$$ it is possible to apply an operation with indices $$$x, y$$$ and $$$z$$$. Then only the first and last occurrences of each element are important.
For all pairs $$$(x, y)$$$ such that $$$1 \le x < y \le m$$$, $$$a_x = a_y$$$, $$$a_x$$$ is the first occurrence and $$$a_y$$$ the last occurrence of that value, a segment $$$[x, y]$$$ will be created.
Let's denote the left border of a segment $$$i$$$ as $$$l_i$$$ and the right border as $$$r_i$$$.
Let's say that a set of segments $$$S$$$ is connected if the union of its segments is the segment $$$[\min(l_i, \forall i\in{S}), \max(r_i, \forall i\in{S})]$$$.
Instead of maximizing $$$\sum\limits_1^m{c_i}$$$, it is possible to focus on minimizing $$$\sum\limits_1^m{[c_i=0]}$$$.
Lemma 1: If we have a connected set $$$S$$$, it is possible to apply some operations to its induced array to end up with at most $$$|S|+1$$$ elements with $$$c_i = 0$$$.
Proof:
For each segment $$$x$$$ in $$$S$$$ if there exists a segment $$$y$$$ such that $$$l_y < l_x < r_x < r_y$$$, it is possible to apply the operation with indices $$$l_y, l_x, r_y$$$ and with $$$l_y, r_x, r_y$$$. Otherwise, add this segment to a set $$$T$$$.
Then is possible to repeatedly select the leftmost segment of $$$T$$$ that have not been selected yet, and set the color of its right border to $$$1$$$, this will be always possible until we select the rightmost segment since $$$T$$$ is connected.
In the end, all the left borders of the segments of $$$T$$$ will have $$$c_i = 0$$$, the same holds for the right border of the rightmost segment of $$$T$$$, which leads to a total of $$$|T|+1$$$ elements with $$$c_i = 0$$$, and $$$|T| \le |S|$$$.
End of proof.
Let $$$X$$$ be a subarray that can be obtained by applying the given operation to the initial subarray any number of times.
Let $$$S(X)$$$ be the set of segments that includes all segments $$$i$$$ such that $$$c[l_i] = 0$$$ or $$$c[r_i] = 0$$$ (or both), where $$$c[i]$$$ is the color of the $$$i$$$-th segment of the subarray $$$X$$$.
Lemma 2: There is always an optimal solution in which $$$S(X)$$$ is connected.
Proof:
Suppose $$$S(X)$$$ is not connected, if there are only two components of segments $$$A$$$ and $$$B$$$, there will always be a segment from $$$A$$$ to $$$B$$$ due to the way the subarray was formed.
If $$$A$$$ or $$$B$$$ have some segment $$$x$$$ such that there exists a segment $$$y$$$ such that $$$l_y < l_x < r_x < r_y$$$ you can erase it by applying the operation with indices $$$l_y, l_x, r_y$$$ and with $$$l_y, r_x, r_y$$$. Then we can assume that $$$\sum\limits_{i\in A}{([c[l_i]=0]+[c[r_i]=0])} = |A|+1$$$ and similarly for $$$B$$$.
The solution to $$$A$$$ before merging is $$$|A|+1$$$, the solution to $$$B$$$ is $$$|B|+1$$$, if we merge $$$A$$$ and $$$B$$$ with a segment we get a component $$$C$$$ of size $$$|A|+|B|+1$$$, and its answer will be $$$|A|+|B|+1+1$$$ (using lemma 1), the case with more than two components is similar, then we can always merge the components without making the answer worse.
End of proof.
Finally, the problem in each subarray can be reduced to find the smallest set (in number of segments), such that the union of its segments is the whole subarray. This can be computed with dp or sweep line.
DP solution:
Let $$$dp[x]$$$ be the minimum size of a set such that the union of its segments is the segment $$$[1,x]$$$.
To compute $$$dp$$$, process all the segments in increasing order of $$$r_i$$$, and compute the value of $$$dp[r_i] = \min(dp[l_i+1], dp[l_i+2], ..., dp[r_i-1]) + 1$$$.
Then the solution to the subarray is $$$dp[m] + 1$$$, this $$$dp$$$ can be computed in $$$O(m\log{m})$$$ with segment tree.
It is possible to compute a similar $$$dp$$$ to solve the problem for the whole array without splitting the array, the time complexity is $$$O(n\log{n})$$$.
Sweep line solution:
It is possible to create an event where a segment starts and an event where a segment ends.
Then process the events in order and each time a segment ends, if it is the rightmost segment added, add to the solution the segment with maximum $$$r_i$$$ among the segments that $$$l_i$$$ is already processed.
It is possible to modify the sweep line to solve the problem for the whole array without splitting the array, the time complexity is $$$O(n)$$$ or $$$O(n\log{n})$$$ depending on the implementation.