CF1270H Number of Components

假设有一个包含 $n$ 个互不相同数字的数组 $a_1, a_2, \dots, a_n$。我们以如下方式在 $n$ 个顶点上构建一张图：对于每一对顶点 $i < j$，如果 $a_i < a_j$，则在 $i$ 和 $j$ 之间连一条边。我们定义该数组的“权值”为这张图中的连通块数量。例如，数组 $[1, 4, 2]$ 的权值为 $1$，数组 $[5, 4, 3]$ 的权值为 $3$。 你需要进行 $q$ 次如下操作：将数组中某个位置的值修改为另一个值。每次操作后，输出当前数组的权值。每次修改是累积的（即修改会影响后续操作）。

第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 5 \cdot 10^5$），分别表示数组的长度和操作次数。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^6$），表示初始数组。 接下来的 $q$ 行，每行包含两个整数 $pos$ 和 $x$（$1 \le pos \le n$，$1 \le x \le 10^6, x \ne a_{pos}$），表示将 $a_{pos}$ 修改为 $x$。 保证在任意时刻，数组中的所有元素都互不相同。

每次操作后，输出当前数组的权值。

第一次操作后，数组变为 $[25, 40, 30, 20, 10]$，权值为 $3$。 第二次操作后，数组变为 $[25, 40, 45, 20, 10]$，权值仍为 $3$。 第三次操作后，数组变为 $[48, 40, 45, 20, 10]$，权值为 $4$。 由 ChatGPT 4.1 翻译