luogu#P3149. 排序
排序
题目描述
有 个人依次站在小 A 面前。小 A 会依次对这 个人进行 次操作。
每次操作选择一个位置 ,将这 个人中的所有身高小于等于当前 位置的人的身高的人从队伍里拎出,然后按照身高从矮到高的顺序从左到右依次插入到 这些人原本的位置当中。
小 A 对这 个人身高构成的序列的逆序对很感兴趣。现在小 A 想要知道每一次操作后这个序列的逆序对数。
Update(2021-01-17): 序列中的逆序对的定义是满足 且 的数对 。
输入格式
第一行两个整数 和 ,表示人数和操作数。
接下来一行 个整数 ,表示初始状态从左到右每个人的身高。
接下来 行每行一个数,表示这次操作的 。
输出格式
输出共 行,第一行表示未操作时的逆序对数量。
除第一行外第 行表示第 次操作后序列的逆序对数。
5 2
1 5 3 4 2
3
4
5
4
3
提示
【样例解释 #1】
第一次操作后序列为 。
第二次操作后序列为 。
【数据范围】
对于 的数据,,,。