← 返回题目列表

Codeforces · 1209/G2

G2. 成块(硬版)

中文机器翻译题面 查看原题

这是问题的更难版本。在此版本中$$$q \le 200\,000$$$。

如果整数序列的元素像 $$$[3, 3, 3, 4, 1, 1]$$$ 那样排列在块中,则该整数序列称为“nice”。形式上,如果两个元素相等,则其间的所有元素也必须相等。

让我们将序列的难度定义为要更改以获得良好序列的最小可能元素数量。但是,如果您将值 $$$x$$$ 的至少一个元素更改为值 $$$y$$$,则还必须将值 $$$x$$$ 的所有其他元素也更改为 $$$y$$$。例如,对于 $$$[3, 3, 1, 3, 2, 1, 2]$$$,不允许将第一个 $$$1$$$ 更改为 $$$3$$$,将第二个 $$$1$$$ 更改为 $$$2$$$。您需要保持 $$$1$$$ 不变或将它们更改为相同的值。

您将获得一系列整数 $$$a_1、a_2、\ldots、a_n$$$ 和 $$$q$$$ 更新。

每次更新的形式为“$$$i$$$ $$$x$$$”——将 $$$a_i$$$ 更改为 $$$x$$$。更新不是独立的(更改会保留到未来)。

打印初始序列和每次更新后序列的难度。

输入

第一行包含整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n \le 200\,000$$$, $$$0 \le q \le 200\,000$$$)、序列长度和更新次数。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 200\,000$$$),初始序列。

以下 $$$q$$$ 行中的每一行都包含整数 $$$i_t$$$ 和 $$$x_t$$$ ($$$1 \le i_t \le n$$$, $$$1 \le x_t \le 200\,000$$$)、位置以及该位置的新值。

输出

打印 $$$q+1$$$ 整数、初始序列的答案以及每次更新后的答案。

示例

输入 #1

5 6
1 2 1 2 1
2 1
4 1
5 3
2 3
4 2
2 1

输出 #1

2
1
0
0
2
3
0