Skip to content

1149: 排序

题目

题目描述

给定一个长度为 $n$ 序列 $S={v_1,v_2,...,v_n}$ ,其中 $v_i$ 的意义为第 $i$ 个位置的权值,依次进行 $m$ 次操作,每次操作选定一个位置 $k$ ,将 $S$ 中所有权值不大于 $v_k$ 中的所有元素拿出,将其按从小到大的顺序重新插入到这些元素原本的位置当中(例如 $S={1,5,3,4,2}$ ,操作位置选择为3,则新的 $S={1,5,2,4,3}$ )。

现在你需要回答初始时以及每次操作之后的 $S$ 中的逆序对数量,其中两个元素构成一个逆序对当且仅当前面的元素权值严格大于后面的元素权值。

输入格式

第一行两个整数 $n$ 和 $m$ ,表示序列大小和操作数

接下来一行 $n$ 个整数 $v_1,v_2,..v_n$ 表示这个序列中的元素 ​
接下来 $m$ 行每行一个数,表示这次操作的位置 $k$

输出格式

输出 $m+1$ 行,第 $1$ 行表示初始时的逆序对数量,第 $i+1$ 行表示第 $i$ 次操作后的逆序对数量

样例输入

text 5 2 1 5 3 4 2 3 4

样例输出

text 5 4 3

数据范围

$1\leq n, m\leq 3 \times 10^5$, $1\leq k\leq n$, $1\leq v_i\leq 10^9$

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!