Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom1年前

07/29
10:14
cdq分治 树状数组

[bzoj 3295] [Cqoi2011] 动态逆序对

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

输入第一行包含两个整数nm,即初始元素的个数和删除的元素个数。以下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分治,可以把删除操作当成插入来看,那么每个数就有3个维度:x位置,v原来的值,t插入的时间。对于一个数i,我们要统计所有t<=ti,(x<xi&&y>yi)||(x>xi&&y<yi)的数量,代表这个数对总逆序对数的贡献。

最外层可以按照x进行排序,然后对t进行分治,y用树状数组维护就行了

 

[bzoj 3295] [Cqoi2011] 动态逆序对