admin 管理员组

文章数量: 1086019

学习笔记——CDQ分治

再次感谢这位大佬的博客：.html

 

CDQ分治，是一种在分治合并中计算前面值对后面答案的贡献的一种算法。今天主要围绕多维偏序问题来对CDQ分治进行介绍

先定义偏序：（以下转载自百度百科）

设R是集合A上的一个关系，如果R是自反的、反对称的和可传递的，则称R是集合A的偏序关系，简称偏序

（1）自反性：a≤a，∀a∈P； （2）反对称性：∀a，b∈P，若a≤b且b≤a，则a=b； （3）传递性：∀a，b，c∈P，若a≤b且b≤c，则a≤c；

 

二维偏序：给定n个二元组，求有多少对二元组满足$a[i].x>=a[j].x$，且$a[i].y>=a[j].y$

暴力$n^{2}$肯定不行，我们可以采用归并排序的方法，对第一维从小到大进行排序，这样只会前面影响后面，然后我们再用类似于“逆序对”的方法统计第二就可以啦~~

拓展题：CF957E（怎么用二维偏序自己想哦~&#

本文标签： 学习笔记CDQ分治

版权声明：本文标题：学习笔记——CDQ分治 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1686560638a10405.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。