打开CDQ的大门&BZOJ3262

题目传送门

第一次接触CDQ分治,感谢YZ大佬的教导。

CDQ分治就是一种奇特的分治方法,它用左区间的区间信息来更新右区间。

设CDQ(L,R,l,r)表示递归到区间[L,R],区间的值为[l,r]。

mid=(l+r)/2。

将L~R区间按<=mid和>mid的两块重新分开。

继续递归区间分治。

CDQ分治用于解决一类偏序问题,题目中所求的为三维偏序。

即计算一类的贡献。

普通的二维偏序大家都做过,经典题目逆序对。

三维怎么做呢?

第一维依然是SORT,第三位是树状数组。

第二维是CDQ。

第一维SORT后有序,故无需考虑第一维。

第二维CDQ分治时枚举L~R区间,当a[i].y>mid时,计算在权值树状数组上的贡献,否则插入树状数组。

注意:这道题需要对重复区间判重,否则贡献值不好算。