← 返回题目列表

Codeforces · 1830/E

E. 欺凌排序

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

在长度为 $$$n$$$ 的排列 $$$p$$$ 上,我们定义欺凌交换如下:

- 令 $$$i$$$ 为最大元素 $$$p_i$$$ 的索引,使得 $$$p_i \neq i$$$。
- 令 $$$j$$$ 为满足 $$$i < j$$$ 的最小元素 $$$p_j$$$ 的索引。
- 交换 $$$p_i$$$ 和 $$$p_j$$$。

我们将 $$$f(p)$$$ 定义为在 $$$p$$$ 排序之前需要执行的欺凌交换次数。请注意,如果 $$$p$$$ 是恒等排列,则 $$$f(p)=0$$$。

给定您 $$$n$$$ 和长度为 $$$n$$$ 的排列 $$$p$$$。您需要处理以下 $$$q$$$ 更新。

在每次更新中,您都会获得两个整数 $$$x$$$ 和 $$$y$$$。您将交换 $$$p_x$$$ 和 $$$p_y$$$,然后找到 $$$f(p)$$$ 的值。

请注意,更新是持久的。对排列 $$$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$$$ 的所有元素都是不同的。

接下来的 $$$q$$$ 输入行的第 $$$i$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i < y_i \le n$$$) — 描述第 $$$i$$$ 更新。

输出

每次更新后,输出$$$f(p)$$$。

示例

输入 #1

8 5
6 2 1 5 3 4 7 8
1 8
2 3
4 7
7 8
3 6

输出 #1

5
6
9
8
7

注意

第一次更新后,我们有 $$$f(p)=5$$$。 $$$5$$$ 霸凌互换如下图所示。

- $$$[\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]$$$。