题意:
给你一个排列,每次拿走一个数,并且询问拿走前有多少逆序对。
题解:
明显是不能暴力的。那么想想逆序对是怎么求解的,逆序对的归并排序的方法本质上就是CDQ分治。所以,现在我们将时间作为新的一维加入逆序对的求解过程中。
令$de[i]$表示时间$i$去掉的那个数会减少多少逆序对。
易得
$de[i]=count\{j|x_j < x_i,y_j>y_i,z_j>z_i\}+count\{j|x_j>x_i,y_j < y_i,z_j>z_i\}$
这样就将这个问题变成了一个三维偏序的问题了。得到以下算法:
- 对x排序
- 对yCDQ分治
- 对z树状数组
代码:
https://github.com/HarryGuo2012/ACMCode/blob/worldLine/UVA/11990.cpp