Description
对于序列A,它的逆序对数定义为满足
i<
j,且A
i>A
j的数对(
i,
j)的个数。给1到
n的一个排列,按照某种顺序依次删除
m个元素,你的任务是在每次删除一个元素之前统计整个序列的逆序对数。
Input
输入第一行包含两个整数
n和
m,即初始元素的个数和删除的元素个数。以下
n行每行包含一个1到
n之间的正整数,即初始排列。以下
m行每行一个正整数,依次为每次删除的元素。
Output
输出包含
m行,依次为删除每个元素之前,逆序对的个数。
Sample Input
5 4
1
5
3
4
2
5
1
4
2
Sample Output
5
2
2
1
样例解释
(1,5,3,4,2)?(1,3,4,2)?(3,4,2)?(3,2)?(3)。
HINT
N<=100000 M<=50000
正解:CDQ分治
解题报告:
CDQ分治裸题。其实也是树套树裸题,然而拿来当CDQ练手吧。
考虑把删除变成倒着插入,那么我给每个坐标一个权值t,表示插入时间。
1 //It is made by ljh2000
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 #include
9 #include
10 #include
11 #include