CF1830E Bully Sort

对于一个长度为 $n$ 的排列 $p$，我们定义一次“bully swap”操作如下： - 找到满足 $p_i \neq i$ 的 $i$ 中 $p_i$ 最大的 $i$。 - 找到满足 $i < j$ 的 $j$ 中 $p_j$ 最小的 $j$。 - 交换 $p_i$ 和 $p_j$。 我们定义 $f(p)$ 为将 $p$ 变为升序排列所需的 bully swap 操作次数。注意，如果 $p$ 已经是升序排列（即恒有 $p_i = i$），则 $f(p)=0$。 现在给定 $n$ 和一个长度为 $n$ 的排列 $p$，你需要处理 $q$ 次操作。 每次操作给定两个整数 $x$ 和 $y$，你需要交换 $p_x$ 和 $p_y$，然后输出当前排列 $p$ 的 $f(p)$。 注意，操作是持续生效的，每次操作后的排列会影响后续操作。

输入的第一行包含两个整数 $n$ 和 $q$（$2 \le n \le 5 \cdot 10^5$，$1 \le q \le 5 \cdot 10^4$），分别表示排列的长度和操作次数。 第二行包含 $n$ 个整数 $p_1,p_2,\ldots,p_n$（$1 \leq p_i \leq n$），表示排列 $p$。所有 $p_i$ 互不相同。 接下来的 $q$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i < y_i \le n$），表示第 $i$ 次操作。

每次操作后，输出当前排列 $p$ 的 $f(p)$。

第一次操作后，$f(p)=5$。下面是 $5$ 次 bully swap 操作的过程： - $[ \mathbf{1}, 2, \mathbf{8}, 5, 3, 4, 7, 6 ]$， - $[ 1, 2, \mathbf{3}, 5, \mathbf{8}, 4, 7, 6 ]$， - $[ 1, 2, 3, 5, \mathbf{4}, \mathbf{8}, 7, 6 ]$， - $[ 1, 2, 3, 5, 4, \mathbf{6}, 7, \mathbf{8} ]$， - $[ 1, 2, 3, \mathbf{4}, \mathbf{5}, 6, 7, 8 ]$。 由 ChatGPT 4.1 翻译