兰州企业网站建设哪家好php网站的首页

是的，如标题所见，本文章会以作者所理解的整体二分思想来介绍一系列整体二分食用方法。

一下内容均是作者本人理解，可能会与算法本身冲突。

1 本质

1.1 板子及从中的启发

我们在做主席树板子的时候，如果使用整体二分，我们将序列 $A$ 与查询的 $l$ 和 $r$ 打包丢到整体二分这个分治结构上去时，会发现，他就类似于一个值域线段树，每一个根节点都有一个树状数组，当满足 $a_i\le mid$ 时该值的下表 $+1$，这也就变成了一个在未可持久化的权值线段树上二分。当然这只是 $nlo{g}^{2}n$ 的做法，当然还有 $nlogn$ 的做法。我们会发现树状数组完全是可以省略掉的，注意到树状数组的修改总是在查询操作前停止，所以我们可以再查询之前将递归到此的序列先用前缀和，再查询，他并不会影响答案。

最后我们会发现若需在线，我们仅需将当前的每个子树的根节点上动态存在的树状数组用平衡树存下来，就可以在使用 $nlogn$ 的空间下完成在线。（此空间当限此题）

2 运用

2.1 三维偏序

所以有了这个近似于树套树的一个理解，我们就可以将他拿去写偏序题目，如：三维偏序（陌上开花）。那这该怎么进行操作呢？

首先排序去掉一维，其次我们可以通过上述的类权值线段树的结构查找小于等于第二维的那些子树的根节点，再去查找记录了这些根节点的树状数组所存储的子树内的序列元素的第三维（以他们第三维为下标并 $+1$），然后再在每个树状数组查询小于等于第三维的个数。这样就结束了朴素的三维偏序。

2.2 三维偏序带二分

那为什么，我会将其称之为朴素？

区间 mex

给出了答案。

我们需要在整体二分类权值线段树这个结构上二分，而树状数组在这个子树维护的元素 $L$ 到 $R$ 中，每个元素的个数是否不为 0。

这显然是一个带着三维偏序条件的二分。

2.3

构造具有单调性的序列，这个就应该不需要多说了吧，显然当成 $N$ 次二分，check 为贪心。

3 拓展

那么在刚开始所介绍的在线方法，是为 此题 的写法做了一个铺垫。

显然 dp 转移是一个三维偏序，但是若用整体二分进行转移会发现当求解 $d{p}_i$ 时，我们需要得到 $[1,i-1]$ 这个区间的所有 dp 值，所以需要在线处理。

那么显然我们可以将原本三维偏序板子代码中的树状数组改成平衡树，在加上一个修改，这就结束了。

十分的简单呀。

但是为什么会说空间复杂度要单独考虑。

思考一个问题：如果是查多次全局第 $k$ 呢？

那么显然树状数组就变成的一个变量，那么在线也只需要一个变量。（这不是就真的成了值域线段树了吗……）

另外有一种做法，我感觉像 cdq 就没写进来，就先这样结束吧。

以上题目我的题解：

1. 三维偏序
2. mex
3. 序列

应该会比这个文章详细一点。

感觉自己写的好抽象啊