网站要懂代码,互联网品牌有哪些,网站开发毕业设计,苏州高端网站设计定制是的#xff0c;如标题所见#xff0c;本文章会以作者所理解的整体二分思想来介绍一系列整体二分食用方法。
一下内容均是作者本人理解#xff0c;可能会与算法本身冲突。
1 本质
1.1 板子及从中的启发
我们在做主席树板子的时候#xff0c;如果使用整体二分#xff0…是的如标题所见本文章会以作者所理解的整体二分思想来介绍一系列整体二分食用方法。
一下内容均是作者本人理解可能会与算法本身冲突。
1 本质
1.1 板子及从中的启发
我们在做主席树板子的时候如果使用整体二分我们将序列 A A A 与查询的 l l l 和 r r r 打包丢到整体二分这个分治结构上去时会发现他就类似于一个值域线段树每一个根节点都有一个树状数组当满足 a i ≤ m i d a_i \leq mid ai≤mid 时该值的下表 1 1 1这也就变成了一个在未可持久化的权值线段树上二分。当然这只是 n l o g 2 n nlog^2n nlog2n 的做法当然还有 n l o g n nlogn nlogn 的做法。我们会发现树状数组完全是可以省略掉的注意到树状数组的修改总是在查询操作前停止所以我们可以再查询之前将递归到此的序列先用前缀和再查询他并不会影响答案。
最后我们会发现若需在线我们仅需将当前的每个子树的根节点上动态存在的树状数组用平衡树存下来就可以在使用 n l o g n nlogn nlogn 的空间下完成在线。此空间当限此题
2 运用
2.1 三维偏序
所以有了这个近似于树套树的一个理解我们就可以将他拿去写偏序题目如三维偏序陌上开花。那这该怎么进行操作呢
首先排序去掉一维其次我们可以通过上述的类权值线段树的结构查找小于等于第二维的那些子树的根节点再去查找记录了这些根节点的树状数组所存储的子树内的序列元素的第三维以他们第三维为下标并 1 1 1然后再在每个树状数组查询小于等于第三维的个数。这样就结束了朴素的三维偏序。
2.2 三维偏序带二分
那为什么我会将其称之为朴素
区间 mex
给出了答案。
我们需要在整体二分类权值线段树这个结构上二分而树状数组在这个子树维护的元素 L L L 到 R R R 中每个元素的个数是否不为 0。
这显然是一个带着三维偏序条件的二分。
2.3
构造具有单调性的序列这个就应该不需要多说了吧显然当成 N N N 次二分check 为贪心。
3 拓展
那么在刚开始所介绍的在线方法是为 此题 的写法做了一个铺垫。
显然 dp 转移是一个三维偏序但是若用整体二分进行转移会发现当求解 d p i dp_i dpi 时我们需要得到 [ 1 , i − 1 ] [1,i-1] [1,i−1] 这个区间的所有 dp 值所以需要在线处理。
那么显然我们可以将原本三维偏序板子代码中的树状数组改成平衡树在加上一个修改这就结束了。
十分的简单呀。
但是为什么会说空间复杂度要单独考虑。
思考一个问题如果是查多次全局第 k k k 呢
那么显然树状数组就变成的一个变量那么在线也只需要一个变量。这不是就真的成了值域线段树了吗……
另外有一种做法我感觉像 cdq 就没写进来就先这样结束吧。
以上题目我的题解
三维偏序mex序列
应该会比这个文章详细一点。
感觉自己写的好抽象啊
