310419: CF1830E. Bully Sort
Description
On a permutation $p$ of length $n$, we define a bully swap as follows:
- Let $i$ be the index of the largest element $p_i$ such that $p_i \neq i$.
- Let $j$ be the index of the smallest element $p_j$ such that $i < j$.
- Swap $p_i$ and $p_j$.
We define $f(p)$ as the number of bully swaps we need to perform until $p$ becomes sorted. Note that if $p$ is the identity permutation, $f(p)=0$.
You are given $n$ and a permutation $p$ of length $n$. You need to process the following $q$ updates.
In each update, you are given two integers $x$ and $y$. You will swap $p_x$ and $p_y$ and then find the value of $f(p)$.
Note that the updates are persistent. Changes made to the permutation $p$ will apply when processing future updates.
InputThe first line of the input contains two integers $n$ and $q$ ($2 \le n \le 5 \cdot 10^5$, $1 \le q \le 5 \cdot 10^4$) — the length of the permutation and the number of updates.
The second line of input contains $n$ integer $p_1,p_2,\ldots,p_n$ ($1 \leq p_i \leq n$) — the permutation $p$. All elements of $p$ are distinct.
The $i$-th of the next $q$ lines of input contains two integers $x_i$ and $y_i$ ($1 \le x_i < y_i \le n$) — describing the $i$-th update.
OutputAfter each update, output $f(p)$.
ExampleInput8 5 6 2 1 5 3 4 7 8 1 8 2 3 4 7 7 8 3 6Output
5 6 9 8 7Note
After the first update, we have $f(p)=5$. The $5$ bully swaps are illustrated below.
- $[\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]$.
Input
题意翻译
对于一个非升序的排列 $\{p_i\}$，定义一次操作为按顺序执行以下步骤： 1. 令 $p_i$ 为排列中最大的满足 $p_i\neq i$ 的数。 2. 令 $p_j$ 为排列中最小的满足 $i<j$ 的数。 3. 交换 $p_i$ 和 $p_j$ 可以证明在排列非升序的前提下总能找到满足条件的 $i$ 和 $j$。 定义一个排列的权值为将其升序排序所需的操作次数，可以证明总能在有限次操作内将其升序排序，注意如果排列本身就是升序的那么其权值为零。 现在给定一个排列和若干次修改操作，求出每次修改后排列的权值，每个修改操作为交换排列中指定的两个数。 注意修改是永久的。Output
给定一个长度为n的排列p，定义一个“霸王交换”如下：
1. 找到最大的元素p_i（i不等于p_i）的索引i。
2. 找到最小的元素p_j（i
定义f(p)为使p有序需要进行的“霸王交换”次数。如果p是单位排列，则f(p)=0。
输入数据格式：
第一行包含两个整数n和q（2≤n≤5×10^5，1≤q≤5×10^4）——排列的长度和更新次数。
第二行输入包含n个整数p_1,p_2,…,p_n（1≤p_i≤n）——排列p。p的所有元素都是不同的。
接下来的q行，每行包含两个整数x_i和y_i（1≤x_i
输出数据格式：
每次更新后，输出f(p)。
示例：
输入：
8 5
6 2 1 5 3 4 7 8
1 8
2 3
4 7
7 8
3 6
输出：
5
6
9
8
7
注意：
第一次更新后，我们得到f(p)=5。下面展示了5次“霸王交换”。
1. [1, 2, 8, 5, 3, 4, 7, 6],
2. [1, 2, 3, 5, 8, 4, 7, 6],
3. [1, 2, 3, 5, 4, 8, 7, 6],
4. [1, 2, 3, 5, 4, 6, 7, 8],
5. [1, 2, 3, 4, 5, 6, 7, 8]。题目大意： 给定一个长度为n的排列p，定义一个“霸王交换”如下： 1. 找到最大的元素p_i（i不等于p_i）的索引i。 2. 找到最小的元素p_j（i