#1624. [CQOI2011] 动态逆序对

[CQOI2011] 动态逆序对

题目描述

对于序列 aa,它的逆序对数定义为集合

{(i,j)i<jai>aj}\{(i,j)| i<j \wedge a_i > a_j \}

中的元素个数。

现在给出 1n1\sim n 的一个排列,按照某种顺序依次删除 mm 个元素,你的任务是在每次删除一个元素之前统计整个序列的逆序对数。

输入格式

第一行包含两个整数 nnmm,即初始元素的个数和删除的元素个数。 以下 nn 行,每行包含一个 1n1 \sim n 之间的正整数,即初始排列。 接下来 mm 行,每行一个正整数,依次为每次删除的元素。

输出格式

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

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

提示

【数据范围】 对于 100%100\% 的数据,1n1051\le n \le 10^51m500001\le m \le 50000

【样例解释】 删除每个元素之前的序列依次为:

1,5,3,4,21,5,3,4,2 1,3,4,21,3,4,2 3,4,23,4,2 3,23,2