更多的分治

六月 16, 2021

分治

引入

什么是分治？

分治就是把一个整体的问题拆成许多小的问题的措施。

Part 1

简单的分治：

二分查找、二分答案、三分求极值、~~点分治、边分治~~

用分治的前提：

1.数据必须是有序的。

2.答案的性质必须是单调的。

二分查找

归并排序、查询特定值(lower_bound:喵喵喵？)

二分答案

对于一些不宜直接求出答案的题，我们可以采用枚举答案的方式，判断答案是否合法，但我们想想，答案肯定不能依次枚举，因为时间复杂度会十分不美观，我们采用二分的方法枚举答案，因为答案一定是有序且包含的，所以这种方法是可行的。

进击的奶牛

$m$ 只奶牛要住在 $n$ 个牛棚里，选择一些牛棚使得相邻两只奶牛之间的最小距离最大。

很显然我们在这题的数据中不能直接得到正确的答案，所以我们只能枚举答案看是否符合样例中的距离，所以我们可以使用二分代替枚举，每次枚举一个可能的答案，看答案是否符合样例（贪心法是可以使用的（证明）），从而得到最大的答案。

跳石头

选择好了两块岩石作为起点和终点。在起点和终点之间，有 $N$ 块岩石（不含起点和终点的岩石）。在比赛中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。

移走一些岩石，使得在比赛中的最短跳跃距离尽可能长。至多从起点和终点之间移走 $M$ 块岩石（不能移走起点和终点的岩石）。

我们直接枚举最大的答案，每次发现情况与当前的答案不合法时就移走一块岩石，直到能够跳到终点或失败，同时更新我们的答案，最后的答案就是你要找的那一个。

砍树

伐木工人米尔科需要砍倒 $M$ 米长的木材。米尔科设置一个高度参数 $H$ （米），伐木机升起一个巨大的锯片到高度 $H$ ，并锯掉所有的树比 $H$ 高的部分（当然，树木不高于 $H$ 米的部分保持不变）。帮助米尔科找到伐木机锯片的最大的整数高度 $H$ ，使得他能得到木材至少为 $M$ 米。换句话说，如果再升高 1 米，则他将得不到 $M$ 米木材。

同样的分析方法，我们枚举 $H$ 的值，然后把树以这个高度砍掉，看一眼长度是否够用，以此类推找到最终的答案。

Part 2

小引入二维偏序问题

给定多个二元组 $(x_{i},y_{i})$ ，求满足 $x_{i}<x_{j}$ ，且 $y_{i}<y_{j}$ 的组数。

说白了就是求逆序对，

那么我们现在选择一名幸运观众说说怎么写归并排序。

CDQ分治

三维偏序

P3810 【模板】三维偏序（陌上花开）

给定多个二元组 $(x_{i},y_{i},z_{i})$ ，对于每个 $i$ ， $f(i)=$ 满足 $x_{i}>x_{j},y_{i}>y_{j}$ ，且 $z_{i}>z_{j}$ 的 $j$ 的数量。

对于 $d \in [0,n)$ ，求 $f(i)=d$ 的 $i$ 的数量。

这个时候就需要我们用到 CDQ 分治了。

那么 CDQ 是什么？

CDQ，指陈丹琪（国家集训队队员）。

简而言之就是个大佬，然后大佬的算法广为流传，就叫这个名字了。

以后可能会有 $0-dp$ （逃

好，我们现在已经有解决二维偏序的经验了，那么…

我们先按每个元素的属性 $a$ 排个序，然后第二维用归并排序，第三维用树状数组。

我们在归并的时候考虑 $[l,mid]$ 对 $[mid+1,r]$ 的贡献。因为我们已经按属性 $a$ 排过序了，所以在排序属性 $b$ 的时候，无论属性 $a$ 怎么被打乱， $[mid+1,r]$ 所有元素的属性 $a$ 一定不小于 $[l,mid]$ 中所有元素的属性 $a$ ，所以第二维是成立的。

在满足前两维都是有序的时候，类似二维偏序的解法，我们可以用树状数组来统计答案了。

四维偏序？？？

我们先从一个 CDQ 开始，那么第一维采用 CDQ，第二维照样使用归并排序，至于最后的统计就变为了一个二元组 $(c_i,d_i)$ 的统计，对于这个问题，我们可以采用树套树的方式解决。

树套树！！！

傻孩子，快跑！

让我们回到三维偏序中，在偏序过程中，我们实际上是进行了对于三元组 $(L,b,c)$ 与 $(R,b,c)$ 进行了处理，其中，一个三元组能对另一个三元组做出贡献，当且仅当 $L$ 中的 $b$ 小于 $R$ 中的 $b$ ， $c$ 同理。于是四维偏序中也存在四元组 $(L,b,c,d)$ 和 $(R,b,c,d)$ ，于是我们先将 $a$ 标记（是左区间还是右区间），再将 $b$ 进行排序，这样以后 $a$ 便是无序的，但我们已经将 $a$ 标记，而且由三维偏序得 $L$ 对 $R$ 做出贡献，所以我们的三元组变为了 $(L,L/R,c,d)$ 和 $(R,L/R,c,d)$ ，其中只有 $(L,L,c,d)$ 对 $(R,R,c,d)$ 做出贡献，于是现在将 $c,d$ 按照三维偏序过程进行处理即可。

更高维的偏序？

这边建议您使用 bitset 或者 KD-tree 呢~

cdq时间复杂度 $O(nlog^kn)$

bitset时间复杂度 $O(kn\sqrt{n})$

KD-tree时间复杂度 $O(n^{1-\frac{1}{k}}+m)$ （来源于网络）

硬套也行，炸了不行。

整体二分

先考虑一个问题：

给定一个数列，查询一次第 $K$ 小的值。

解法一：直接排序，然后找下标为 $K$ 的数。

解法二：用一颗权值线段树，插进去后二分进行查找。

我们把这个问题升级一下：给定一个数列，查询多次第 $K$ 小的值。

解法一未受到太大影响，但是解法二如果多次询问直接挂掉，这时候就需要整体二分了！

分析

回到二分查找的本质，我们每次猜测一个数 $mid$ ，随后如果猜大了往前，猜小了往后，那么我们可以猜测所有的数都是 $mid$ ，如果 $mid$ 小于 $K$ ，直接搞到右区间，同时将 $K-=sum_{left}$ ，如果大于等于 $K$ ，我们直接拉到左区间，如果最后 $l==r$ ，那么结束这个部分的二分。

void solve(int l, int r, vector<Query> q) {
  int m = (l + r) / 2;
  if (l == r) {
    for (unsigned i = 0; i < q.size(); i++) ans[q[i].id] = l;
    return;
  }
  vector<int> q1, q2;
  for (unsigned i = 0; i < q.size(); i++)
    if (q[i].k <= check(m))
      q1.push_back(q[i]);
    else
      q[i].k -= check(m), q2.push_back(q[i]);
  solve(l, m, q1), solve(m + 1, r, q2);
  return;
}

那么我们的复杂度就变成了 $O(Tlogn)$ 。（ $T$ 为对应的查询的操作时间复杂度）

再变一变：询问变为查询 $[l,r]$ 中第 $K$ 小的数。

好的排序挂了，但是我们有数据结构啊！

但是我们的整体二分也在 check 函数中出现了问题

——To be continued…

查看评论