CDQ分治,总而言之就是很神奇的分治
在这里引入二位偏序问题(逆序对)
对于一位偏序的解决方法可以理解为CDQ分治(归并排序)
对于二维偏序也就是逆序对可以用树状数组统计,也可以用归并排序统计
对于归并排序就是每次合并两端区间并且操作右区间的时候统计一下左区间剩余多少,这个就可以简单的统计出来答案
对于树状数组,可以按顺序依次读入让树状数组的第a[x]a[x]位置的元素+1+1 即add(a[x],1)add(a[x],1),同时还要防止a[x]a[x]过大因此还要离散化,对于新加入的元素查找前面比他大的元素可以直接ask(n)−ask(a[x])ask(n)−ask(a[x])就可以得到对于这个元素可以与之前的元素构成的逆序对
对于三维偏序,可以首先将第一维排序,然后用跑一遍归并(过程类似,但并不是归并排序)来维护剩下的两维,对于剩下的两维在合并的时候先按照第二维排序,然后将第三维加入树状数组中查询,此步骤入上述逆序对.