U149135 【Minecraft: Story Mode 模拟赛 DLC (1) T2】摆肖像

> "*They're absolutely exquisite! Perfect!*" > > —Ivor when looking at his portrait.

毒死所谓的"旅行家" Torque Dawg 后，「白南瓜头」（White Pumpkin）Cassie Rose 并未在他的库存内发现她想要的宝藏。纵使她十分失望，但是肖像仍然得换。Cassie Rose 传送回她的地下室，拿出打了叉的肖像，跑回大厅。 偌大的大厅里，墙上整齐的排着 $n$ 张肖像，每一张的编号为 $a_1, a_2, \cdots, a_n$。Cassie Rose 上一次作案已经是几年前了，再次回到大厅时，才发现自己已经忘记 Torque Dawg 的肖像摆在哪里了。 Cassie Rose 决定重新布置肖像墙，使得最终肖像墙上，$n$ 张肖像的编号形成一个**不下降序列**。简单点说，就是把这 $n$ 张肖像按编号 $a_i$ 排序。 Cassie Rose 是一名比较菜的 OIer，她最后决定使用**冒泡排序**来达成自己的目的。具体地说，Cassie Rose 会在**每一次检视**中，扫过每一张肖像；如果存在 $i \in [1,n)$，使得 $a_i > a_{i+1}$，那么，Cassie Rose 就会交换第 $i$ 张肖像与第 $i+1$ 张肖像。Cassie Rose 会不断检视，直到这 $n$ 张肖像的编号形成一个**不下降序列**。注意，当序列**已经有序之后**，Cassie Rose **还会进行最后一次检视**，确认序列有序。 由于 Cassie Rose 学过量子波动速读，她每一次检视仅需花费 1 毫秒。但是，新的问题接踵而至： * 这个世界从不太平，府邸内僵尸丛生，三不五时就会有人死亡。 * 由于 Cassie Rose 上一次作案，来到肖像墙时已经是几年前，有一些肖像已经泛黄、破损，需要更换。 这就导致 Cassie Rose **还没开始检视**时，就要**更换一些肖像**。 面对巨量的肖像与更换操作，Cassie Rose 陷入了茫然。于是，她找到了你，希望你帮她计算一下，**每一次更换肖像后**，她需要花费多少毫秒才能完成排序过程。

第一行两个正整数 $n, q$，$n$ 表示肖像的张数，$q$ 表示更换肖像的次数。 第二行，$n$ 个正整数 $a_1, a_2, \cdots, a_n$。$a_i$ 表示初始时第 $i$ 张肖像的编号。 接下来 $q$ 行，每行两个正整数 $pos, val$，表示这一次更换是把**第 $pos$ 张**肖像更换成**编号为 $val$ 的**肖像。

$q$ 行。表示每一次更换操作后，Cassie Rose 需要多少毫秒，才能完成排序。

**样例解释** 第一次修改中，$a_1$ 的值被改成了 $3$，我们得到了一个肖像数组 $\{3, 2, 3, 4\}$ 第二次修改中，$a_2$ 的值被改成了 $1$，我们得到了一个肖像数组 $\{3, 2, 1, 4\}$ 对于 $\{3, 2, 3, 4\}$ ，Cassie Rose 开始排序： * 第一次检视时，肖像并未有序。因为 $a_1 > a_2$，所以交换这两张肖像得到新的肖像数组 $\{2, 3, 3, 4\}$；因为 $a_2 \leq a_3$，$a_3 \leq a_4$，所以不交换它们。 * 第二次检视时，肖像已经有序，排序完毕。耗时 2 毫秒。 对于 $\{3, 2, 1, 4\}$ ，Cassie Rose 开始排序： * 第一次检视时，肖像并未有序。因为 $a_1 > a_2$，所以交换这两张肖像得到新的肖像数组 $\{2, 3, 1, 4\}$；因为 $a_2 > a_3$，所以交换这两张肖像得到新的肖像数组 $\{2, 1, 3, 4\}$；因为 $a_3 \leq a_4$，所以不交换它们。 * 第二次检视时，肖像并未有序。因为 $a_1 > a_2$，所以交换这两张肖像得到新的肖像数组 $\{1, 2, 3, 4\}$；因为 $a_2 \leq a_3$，$a_3 \leq a_4$，所以不交换它们。 * 第三次检视时，肖像已经有序，排序完毕。耗时 3 毫秒。 **数据范围** 对于 $100\%$ 的数据，$1 \leq n, q \leq 5 \times 10^5$，$1 \leq a_i,val \leq 10^9$，$1 \leq pos \leq n$。完整的数据规模详见下表： | 测试点编号 | $n$ | $q$ | $a_i, val$ | | ---------- | -------------------- | -------------------- | -------------------- | | 1 | $\leq 5 \times 10^5$ | $=0$ | $\leq 10^9$ | | 2 | $\leq 200$ | $=1$ | $\leq 10^3$ | | 3 | $\leq 200$ | $\leq 100$ | $\leq 10^3$ | | 4 | $\leq 200$ | $\leq 200$ | $\leq 10^6$ | | 5 | $\leq 200$ | $\leq 200$ | $\leq 10^9$ | | 6 | $\leq 200$ | $\leq 200$ | $\leq 10^9$ | | 7 | $\leq 4000$ | $\leq 4000$ | $\leq 10^6$ | | 8 | $\leq 6000$ | $\leq 6000$ | $\leq 10^9$ | | 9 | $\leq 8000$ | $\leq 8000$ | $\leq 10^9$ | | 10 | $\leq 8000$ | $\leq 8000$ | $\leq 10^9$ | | 11 | $\leq 8000$ | $\leq 8000$ | $\leq 10^9$ | | 12 | $\leq 5 \times 10^4$ | $\leq 5 \times 10^4$ | $\leq 100$ | | 13 | $\leq 5 \times 10^4$ | $\leq 5 \times 10^4$ | $\leq 100$ | | 14 | $\leq 5 \times 10^4$ | $\leq 5 \times 10^4$ | $\leq 100$ | | 15 | $\leq 5 \times 10^4$ | $\leq 5 \times 10^4$ | $\leq 100$ | | 16 | $\leq 2 \times 10^5$ | $\leq 2 \times 10^5$ | $\leq 2 \times 10^5$ | | 17 | $\leq 4 \times 10^5$ | $\leq 4 \times 10^5$ | $\leq 10^9$ | | 18 | $\leq 5 \times 10^5$ | $\leq 5 \times 10^5$ | $\leq 5 \times 10^5$ | | 19 | $\leq 5 \times 10^5$ | $\leq 5 \times 10^5$ | $\leq 10^9$ | | 20 | $\leq 5 \times 10^5$ | $\leq 5 \times 10^5$ | $\leq 10^9$ | **致谢 & 相关信息** 题目来源：IOI 2018 练习赛第三题 **Bubble Sort 2** Original Problem: IOI 2018 Practice Contest, Problem 3, Bubble Sort 2 数据、标程：@fsy_juruo Data & std: @fsy_juruo 审题、验题：@strongduck Verification: @strongduck 题目背景：*Minecraft: Story Mode* 第一季 第六章 Problem Background: *Minecraft: Story Mode* Season I, Episode 6: “A Portal to Mystery”