开始 2022-02-08 12:18:16

20220208分块重现赛

结束 2022-02-28 00:00:00
Contest is over.
当前 2024-12-22 15:28:33

H. [Cqoi2011]动态逆序对

描述

对于序列A,它的逆序对数定义为满足i < j,A_i>A_j的数对(i,j)的个数。给1到n的一个排列,按照某种顺序依次删除m元素,你的任务是在每次删除一个元素之前统计整个序列的逆序对数

输入

输入第一行包含两个整数nm,即初始元素的个数和删除的元素个数。

以下n行每行包含一个1n之间的正整数,即初始排列

以下m行每行一个正整数,依次为每次删除的元素

N\le100000,M\le50000

输出

输出包含m行,依次为删除每个元素之前,逆序对的个数。

样例

输入

5 4
1
5
3
4
2
5
1
4
2

输出

5
2
2
1

提示

样例解释

每次删除之后序列分别是:

(1,5,3,4,2)

(1,3,4,2)

(3,4,2)

(3,2)

(3)


Submit

登录

注册
时间限制 1 秒
内存限制 512 MB
提交