cdq分治

素颜马尾好姑娘i 2021-12-17 07:49 220阅读 0赞

# 0x00 前言 #

话说cdq应该大写还是小写。。。。。

--------------------

# 0x01 什么是cdq分治？ #

设问题区间为\[L,R\]，中点为MID

普通的分治：

1.  递归处理\[L,MID\]
2.  递归处理\[MID+1,R\]
3.  合并答案

cdq分治：

1.  递归处理\[L,MID\]
2.  递归处理\[MID+1,R\]
3.  处理\[L,MID\]区间对\[MID+1,R\]区间的影响

哇听起来好厉害，但是不懂是什么意思啊

--------------------

# 0x02 你在哪里遇见过cdq分治？ #

其实几乎所有人都写过cdq分治

我们考虑一个问题

> ### 问题1 ###
> 
> 给定一个序列，序列中有一些元素，每个元素有两个权值ai，bi，问有多少对元素满足ai>aj，bi<bj

这是一个非常经典的问题（没听说过的话那还是死死掉比较好）

如果ai是1~n的排列的话那就是全裸的逆序对了

考虑用归并排序求解这个问题的过程

*  按ai排序
 *  对bi归并
 *  把一个区间分成左右两半
 *  分别处理左右两半
 *  每次我们需要从右半部分吐出一个元素时，这个元素和左半部分所有剩下的元素构成逆序对

这好像和cdq分治差不多啊？

每次从右半边吐出来一个元素时，统计左边剩下的所有元素对它的影响

恩很对

--------------------

# 0x03 cdq分治的实质？ #

考虑一个新的问题

> ### 问题2 ###
> 
> 给定一个序列，序列中有一些元素，每个元素有两个权值ai，bi，问有多少对元素满足ai>aj，bi>bj

这个应该叫顺序对问题？

做法的话，把刚才求逆序对的方式改一下就行了，没说不能每次统计\[MID+1，R\]区间对\[L,MID\]区间的影响啊

对于这个问题，我们有一个看上去很傻疑问

*  问：为什么不能先按a排一遍序，再按b排一遍序，然后线性扫一遍得出答案？
 *  答：因为对b排序的时候会破坏a的相对关系

然后我们考虑这样的分治做了什么

对\[L,MID\]和\[MID+1,R\]分别归并完后，\[L,MID\]和\[MID+1,R\]现在分别是关于b有序的了，但是关于a无序。精妙的是，\[L,MID\]和\[MID+1,R\]之间关于a是相对有序的。即，\[L,MID\]范围内的a都小于\[MID+1,R\]范围内的a。

妙啊！（拍桌子）

这样就可以直接统计了

--------------------

# 0x04 拓展 #

显然会有下面这种问题

> ### 问题1 ###
> 
> 给定一个序列，序列中有一些元素，每个元素有三个权值ai，bi，ci，问有多少对元素满足ai>aj，bi>bj，ci>cj

这怎么搞？

按照刚才的思路，对a排序，对b cdq分治，c呢？

那就只好上一个二维数据结构了，每次扫描到\[L,MID\]区间内的ci时把ci插入树状数组（或者别的什么东西），扫描到\[MID+1,R\]区间内的ci时在树状数组里查询有多少cj小于它

完美解决

这里我们可以看到，cdq分治思想可以顶一层数据结构。不用cdq分治的话只好树套树了吧。。

--------------------

# 0x05 邪教用法 #

刚才的例子里我们发现cdq分治可以顶一层数据结构，那如果只用一层数据结构的题呢？能不能不用数据结构？

比方说，老年人选手连树状数组都写不动怎么办？

考虑树状数组的经典问题，单点修改，询问区间和

树状数组做区间和查询的时候是拆成前缀和的形式做的，这里我们也拆成前缀和做

数组有初值？没关系，把所有初值改成修改，时间放在最前面。

然后像做逆序对那么搞就行了，ai是时间，bi是位置，统计一下\[L,MID\]区间内的修改的和，在\[MID+1,R\]区间内相应修改

我好懒啊，不想上代码。

上网找别的dalao的代码吧orz，写的比我好多了

--------------------

# 0x06 杂物 #

cdq分治实际上把每个修改统计了logn次

cdq分治的时候你得写归并排序，或者你可以偷懒用sort，复杂度多一个log（这很致命）

cdq分治要求修改相互独立

cdq分治不能处理删除，有删除的话，你可能得倒过来做

cdq分治很短。。。比二层数据结构好写多了

今天的Yayoi依然因为线段树常数太大TLE了

--------------------

# 0x07 例题 #

都是权限题orz

一般来说都是维护三维偏序关系

陌上花开（这好名字真是糟蹋了）

动态逆序对

mokia

转载于:https://www.cnblogs.com/LoveYayoi/p/6745491.html

发表评论取消回复

表情：

评论列表（有 0 条评论，220人围观）

还没有评论，来说两句吧...

相关阅读

相关 cdq分治总结（题目合集）

1、The Preliminary Contest for ICPC Asia Nanjing 2019 A. The beautiful values of the p...

灰太狼/ 2024年04月17日 21:57/ 0 赞/ 23 阅读

相关洛谷P4169 [Violet]天使玩偶/SJY摆棋子(CDQ分治)

\[Violet\]天使玩偶/SJY摆棋子 [题目传送门][Link 1] 解题思路用CDQ分治开了氧气跑过。将输入给的顺序作为第一维的时间，x为第二维，y

秒速五厘米/ 2023年08月17日 17:21/ 0 赞/ 69 阅读

相关【openjudge】C15C Rabbit's Festival【CDQ分治+并查集】

传送门：[【openjudge】C15C Rabbit’s Festival][openjudge_C15C Rabbit_s Festival] 题目分析：考虑到每条边

缺乏、安全感/ 2022年08月05日 00:56/ 0 赞/ 97 阅读

相关 HDU 5324 Boring Class【cdq分治】

这就是一个三维排序的问题，一维递减，两维递增，这种问题用裸的CDQ分治恰好可以解决。如同HDU 4742（三维排序，一个三维都是递增的）因为最小字典序比较麻烦，所以

怼烎@/ 2022年08月03日 00:29/ 0 赞/ 100 阅读

相关 HDU - 5618 Jam's problem again(cdq分治和整体二分)

[点我看题][Link 1] 题意:在三维坐标系中有n个点(x,y,z),对于某两个点i(xi,yi,zi)和j(xj,yj,zj),如果xi>xj且yi>yj且zi>zj,

悠悠/ 2022年06月07日 09:52/ 0 赞/ 128 阅读

相关 codeforces 1046_problem_A AI robots (cdq分治)

[传送门][Link 1] 题意：给n个机器人，机器人都有自己的位置x，可见范围r，智商q，问两个机器人互相可见，并且智商相差不多于k的对数有多少。思路：运用分治思想，第

墨蓝/ 2022年05月10日 03:28/ 0 赞/ 119 阅读

相关 CDQ分治总结

CDQ主要用来解决多维偏序问题，只能用来处理离线问题，复杂度为O(n\(logn)^d)，d为总维度。理解CDQ分治的关键点： 1、只有前面的修改操作会影响后面

浅浅的花香味﹌/ 2022年01月25日 23:53/ 0 赞/ 159 阅读

相关 [BZOJ 1176&COGS 1752][BOI2007]Mokia（CDQ分治+树状数组）

Description 维护一个W\W的矩阵，初始值均为S.每次操作可以增加某格子的权值,或询问某子矩阵的总权值.修改操作数M<=160000,询问数Q<=10000,W<=

逃离我推掉我的手/ 2022年01月12日 01:17/ 0 赞/ 145 阅读

相关 cdq分治

0x00 前言话说cdq应该大写还是小写。。。。。 -------------------- 0x01 什么是cdq分治？设问题区间为\[L,R\]，中点为

素颜马尾好姑娘i/ 2021年12月17日 07:49/ 0 赞/ 221 阅读

相关 BZOJ.1492.[NOI2007]货币兑换(DP 斜率优化 CDQ分治/Splay)

[BZOJ][] [洛谷][Link 1] 如果某天能够赚钱，那么一定会在这天把手上的金券全卖掉。同样如果某天要买，一定会把所有钱花光。那么令\\(f\_i\\)表示

矫情吗；*/ 2021年10月01日 01:24/ 0 赞/ 222 阅读