306521: CF1209F. Koala and Notebook
Memory Limit:0 MB
Time Limit:0 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Into Blocks (easy version)
题意翻译
给你$n~q$,$n$表示序列长度,$q$表示操作次数,在该题中$q$等于0 我们需要达成这么一个目标状态: 如果存在$x$这个元素,那么必须满足所有$x$元素都必须在序列中连续。 然后你可以进行这么一种操作,将所有的$x$元素的变为任意你指定的$y$元素,并且花费$cnt[x]$的花费,$cnt[x]$代表$x$元素的个数。 求最小花费使得序列满足目标状态题目描述
This is an easier version of the next problem. In this version, $ q = 0 $ . A sequence of integers is called nice if its elements are arranged in blocks like in $ [3, 3, 3, 4, 1, 1] $ . Formally, if two elements are equal, everything in between must also be equal. Let's define difficulty of a sequence as a minimum possible number of elements to change to get a nice sequence. However, if you change at least one element of value $ x $ to value $ y $ , you must also change all other elements of value $ x $ into $ y $ as well. For example, for $ [3, 3, 1, 3, 2, 1, 2] $ it isn't allowed to change first $ 1 $ to $ 3 $ and second $ 1 $ to $ 2 $ . You need to leave $ 1 $ 's untouched or change them to the same value. You are given a sequence of integers $ a_1, a_2, \ldots, a_n $ and $ q $ updates. Each update is of form " $ i $ $ x $ " — change $ a_i $ to $ x $ . Updates are not independent (the change stays for the future). Print the difficulty of the initial sequence and of the sequence after every update.输入输出格式
输入格式
The first line contains integers $ n $ and $ q $ ( $ 1 \le n \le 200\,000 $ , $ q = 0 $ ), the length of the sequence and the number of the updates. The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 200\,000 $ ), the initial sequence. Each of the following $ q $ lines contains integers $ i_t $ and $ x_t $ ( $ 1 \le i_t \le n $ , $ 1 \le x_t \le 200\,000 $ ), the position and the new value for this position.
输出格式
Print $ q+1 $ integers, the answer for the initial sequence and the answer after every update.
输入输出样例
输入样例 #1
5 0
3 7 3 7 3
输出样例 #1
2
输入样例 #2
10 0
1 2 1 2 3 1 1 1 50 1
输出样例 #2
4
输入样例 #3
6 0
6 6 3 3 4 4
输出样例 #3
0
输入样例 #4
7 0
3 3 1 3 2 1 2
输出样例 #4
4