C/C++教程

cdq 分治、整体二分、二进制分组以及高维数点问题总结

本文主要是介绍cdq 分治、整体二分、二进制分组以及高维数点问题总结,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

小螺号呀滴滴地吹,ycx 呀 xjb 写。

数据结构非经典算法

cdq 分治

传统分治算法是当前区间分成两个区间递归下去各解决各自的。cdq 分治是不仅把两部分的子问题都解决了,还让左部分对右部分进行贡献(右对左也行?)。如果左对右贡献的时间复杂度仅与当前处理区间长度 \(n\) 有关,并且是其 polylog,设为 \(f(n)\),则总复杂度为 \(\mathrm O(f(n)\log n)\)​(这玩意是上界是显然的,同阶的话就感性理解一下吧,大概要用 master 定理?)。

较常见的应用:

  1. 数线性结构上(树上可以用 cdq 的拓展——点分治,但我还没学/ll)符合某种条件的数对,左对右贡献就是一个在左部分一个在右部分的数量,由于有 \(mid\) 这个大坝在中间隔着,一般比原问题简单得多,代价是一个 log。
  2. 将离线动态数据结构问题转化为离线静态问题,代价是一个 log。前提是修改对询问的贡献有交换律、结合律,而且互相独立。方法是每次左部分的所有修改对右部分的所有询问做贡献,是静态的。
  3. 优化 dp。dp 和二分这两玩意看上去是在线,但又不完全是,所以取名曰「半在线」。所以解决 dp 的这 cdq 事实上是改进版本的 cdq,必须是 solve 了左部分,然后左对右贡献,然后 solve 右部分这样一个顺序。因为必须等左部分 dp 值算好之后才能贡献。

二进制分组

只做过一道题,不常用就是了

cdq 想把动态问题转静态问题,需要允许离线。如果强制在线,我们依然有办法将在线动态问题转化为在线静态问题,以一个 log 的代价,前提也是修改对询问的贡献有交换律、结合律、互相独立。

方法是对任意时刻设目前进行了 \(x\) 次修改,将 \(x\) 二进制拆分,实时对每个位权为 \(i\) 的二进制位维护连续 \(i\) 个修改的预处理成果,位权越小维护的修改越新。新加一个修改的时候,令 \(x\) 加一,取低位极长连续 \(1\) 段,加一就是让这些 \(1\) 全变成 \(0\),然后上一位变成 \(1\),实现就是把这些 \(1\) 位合并起来加上新加修改放到新的 \(1\)​ 位,可以直接暴力重构。这样子等效于在线静态。查询就直接到 \(\log\) 个修改块里面依次查询,把贡献弄起来。

设预处理 \(n\)​ 个修改复杂度为 \(n\) 的 polylog \(f(n)\),复杂度证明:

\[\begin{aligned}\mathrm T(n)&=\sum\limits_{i=1}^nf(\mathrm{lowbit}(i))\\&=\sum\limits_{i=1}^{\lfloor\log_2n\rfloor}f\!\left(2^i\right)\left\lfloor\dfrac{n}{2^i}\right\rfloor\\&=\mathrm O(f(n)\log n)\end{aligned} \]

整体二分

我们知道二分这玩意是「半在线」,如果你就把它当在线做,一次回答一个 chk 的话,那免不了受在线问题的局限,比如要预处理一大堆信息,维护的数据结构套层也比较厚。我们有整体二分算法能加大二分的 chk 们的离线程度,前提是题目允许离线。

考虑把所有待二分询问离线下来存到一个序列里,然后一起二分,一开始将它们的二分范围设成一样然后一起 chk。chk 出来一些分到左边一些分到右边,继续递归下去一起 chk。注意到这里某个二分的 log 步之间还是在线关系,但是若干个二分是平行的,整体二分就利用了这一点充分发挥离线的优势一起 chk。

设处理 \(n\) 个询问的 chk 的复杂度是仅关于 \(n\) 的 polylog \(f(n)\),则总复杂度为 \(\mathrm O(f(n)\log v)\),其中 \(v\) 是二分范围,不劣于传统二分。整体二分过程中可能不止维护询问序列,还维护了一些对 chk 有贡献的修改序列,这时候需要保证它们每次分裂的时候最多被分到一边(询问的话是自然),此时 \(n\) 是所有序列的总长度。另外若 \(v\)​​ 过大,当询问序列为空时要及时停下来,不然复杂度爆炸。

遇到操作 \(x\) 对 \(mid\geq x\) 都有贡献,这时候有可能不能只分到一边这种情况,通常有两种办法:将待 chk 询问及时减掉 \([l,mid]\)​ 的贡献,这样就可以放心的把前面的贡献只分到前面啦;若无法实现「减掉」,可以令 \([l,mid]\) 子问题做完后,\(\leq mid\) 的操作已经被贡献完毕了,实现是该撤销还是撤销,但是到不继续往下递归的时候要把当前操作序列全部贡献上。

高维数点问题

指的是在 \(d\) 维空间中,有若干个点,每个点有个贡献(交换律、结合律、独立),求第 \(i\) 维不超过 \(x_i\) 所有点贡献和。值域 \(v\),动态指的是动态加点。

如果是第 \(i\) 维 \(\in[l_i,r_i]\) 这种限制可以差分转化,当然是在贡献可减的情况下。

离线情况的 cdq

离线静态 \(d\)​ 维数点,可以通过给修改、询问的混合序列按第一维排序(注意排序一定要是稳定的,不然修改可能跑到询问后面去!),就变成了一个 \(d-1\) 维动态数点。而 \(d\) 维动态数点可以以一个 log 的代价变成 \(d\) 维静态数点。按照这个思路递归下去。

边界是静态一维数点,不考虑排序 / 二分复杂度是线性。那么静态 \(d\) 维数点是个 \(d-1\) 个 log,动态就是 \(d\) 个。考虑上排序的话,可以发现维数稍高都被平行化掉了,唯有静态一维增加到了 1log。

其实动态一维写 cdq 就是所谓的「归并排序写逆序对」,为了平行化掉排序还非得归并,直接 stable_sort 是 2log(当然更高维就直接 stable_sort 啦),比较麻烦,还是直接 BIT 好写。

在线情况的线段树套层

在线二维静态可以主席树 1log,更高维的 \(d\) 维静态的套层线段树我也不知道能不能可持久化啊啊啊,反正按动态做 \(d\) 个 log 是没问题。

在线动态的话,\(d\) 维就套 \(d\) 个线段树,最外层可以换成 BIT(除非贡献性质不太好,不可减),里面都是动态开点线段树,不然空间不够。空间 \(d-1\) 个 log,时间 \(d\) 个 log。在线三维动态可以二进制分组套主席树复杂度不变,再高维的话二进制分组转化为静态关键是在线高维静态咱不会做啊 5555

应该没有出题人毒瘤到出在线的高维数点吧(高维指的是 3 维以上)。。。。

bitset 奇技淫巧

如果真的是「数」点,也就是每个点权为 \(1\)​,合并贡献是加法,那有个奇技淫巧。考虑第 \(i\) 维不超过 \(x_i\) 的点的集合,用 bitset 存,然后把 \(d\) 维交起来即可。

实现不需要什么「可持久化 bitset」,直接对每维扫一遍前缀和预处理即可,前提是能存的下。时空复杂度都是 \(\mathrm O\!\left(\dfrac{dn^2}w\right)\)。注意到 \(d\) 这里作为一个因子成在前面,而不是指数,所以维数上升没什么影响。

这篇关于cdq 分治、整体二分、二进制分组以及高维数点问题总结的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!