Official Editorial

Explanation

The key thing to notice here is that if we have two numbers like so:

where their active ranges intersect, then they have to be the same value.

The algorithm is thus to split the array into all the "independent" segments, where no number in the original array is split into multiple segments. We do this by calculating all the value ranges initially and sorting them by start position.

For example, if our initial array was

the segments would be the first five and last four elements of the array.

For each segment, its difficulty is its length minus the number of times the most frequently occurring value appears. In other words, the best strategy is to change every value in the segment to the value that already occurs the most.

The total difficulty is the sum of the difficulties across all segments, since they don't affect each other.

Implementation

Time Complexity: $\mathcal{O}(n \log n)$

Copy
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

int main() {

Copy
import java.io.*;
import java.util.*;

public class IntoBlocks {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer initial = new StringTokenizer(read.readLine());
		int len = Integer.parseInt(initial.nextToken());

		StringTokenizer arrST = new StringTokenizer(read.readLine());

Copy
len_, _ = [int(i) for i in input().split()]

inds = {}
arr = [int(i) for i in input().split()]
for i in range(len_):
	if arr[i] not in inds:
		inds[arr[i]] = []
	inds[arr[i]].append(i)

ranges = []