CF1209G2 Into Blocks (hard version)

这是该问题的更难版本。在本版本中 $q \le 200\,000$。 如果一个整数序列的元素被分成若干块排列，例如 $[3, 3, 3, 4, 1, 1]$，则称该序列为“优美”序列。形式化地说，如果两个元素相等，则它们之间的所有元素也必须相等。 我们定义一个序列的“难度”为：将其变为优美序列所需最少修改的元素个数。然而，如果你将某个值 $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$），表示将第 $i_t$ 个位置的值改为 $x_t$。

输出 $q+1$ 个整数，依次为初始序列和每次操作后的难度。

由 ChatGPT 4.1 翻译