luogu#P3149. 排序

排序

题目描述

nn 个人依次站在小 A 面前。小 A 会依次对这 nn 个人进行 mm 次操作。

每次操作选择一个位置 kk,将这 nn 个人中的所有身高小于等于当前 kk 位置的人的身高的人从队伍里拎出,然后按照身高从矮到高的顺序从左到右依次插入到 这些人原本的位置当中。

小 A 对这 nn 个人身高构成的序列的逆序对很感兴趣。现在小 A 想要知道每一次操作后这个序列的逆序对数。


Update(2021-01-17):aa 序列中的逆序对的定义是满足 i<ji < jai>aja_i > a_j 的数对 (i,j)(i, j)

输入格式

第一行两个整数 nnmm,表示人数和操作数。

接下来一行 nn 个整数 aia_i,表示初始状态从左到右每个人的身高。

接下来 mm 行每行一个数,表示这次操作的 kk

输出格式

输出共 m+1m + 1 行,第一行表示未操作时的逆序对数量。

除第一行外第 ii 行表示第 i1i - 1 次操作后序列的逆序对数。

5 2
1 5 3 4 2
3
4
5
4
3

提示

【样例解释 #1】

第一次操作后序列为 1,5,2,4,31, 5, 2, 4, 3

第二次操作后序列为 1,5,2,3,41, 5, 2, 3, 4

【数据范围】

对于 100%100 \% 的数据,1n,m3×1051 \le n,m \le 3 \times {10}^51kn1 \le k \le n1ai1091 \le a_i \le {10}^9