CDQ 分治、整体二分和对时间分治

Author Avatar
dozbear 5月 23, 2017
  • 在其它设备中阅读本文章

CDQ 分治

一般来讲,用人名命名的算法都是毒瘤

其实 CDQ 分治能做的基本上主席树都能做,数据结构很强的神犇可以 ctrl + w

其实还是可以学一下的,空间上会节省一到两个 \(\log\)

CDQ 分治的核心思想是什么?用已有的结果来更新答案 我知道就算说了也听不懂当我没讲

先看一道题吧

BZOJ 3263

给定 \(n\) 个三元组,对于每个三元组 \((A_i,B_i,C_i)\),求满足 \(A_i \le A_j,B_i \le B_j,C_i \le C_j\) 的 \(j\) 的个数。

\(n \le 10^5,\ \max(A_i,B_i,C_i) \le 2 \times 10^5\)

先按照 \(A_i\) 排序,然后设 \(solve(l,r)\) 为单独统计出区间 \(\left[l,\ r \right)\) 中每个元素对此区间内其他元素的答案

那么对于 \(solve(l,r)\) ,我们在做完 \(solve(l,mid)\) 和 \(solve(mid,r)\) 后,在区间 \([l,mid)\) 内的每个元素上打一个标记,再按照 \(B_i\) 对 \([l,r)\) 中元素排序,从头扫到尾,使用一个树状数组来帮助统计:对于每个元素,如果有标记,就在树状数组的 \(C_i\) 位置 \(+1\) ,否则从 \(C_i\) 位置查询前缀和并加入到此三元组的答案中

简而言之,就是分治然后统计区间前一半对后一半的贡献 (我也不知道该怎么说了

时间复杂度 \(\Theta(n \log^2 n)\)

BZOJ 3456

刚刚解决完电力网络的问题,阿狸又被领导的任务给难住了。

刚才说过, 阿狸的国家有n个城市,现在国家需要在某些城市对之间建立一些贸易路线,使得整个国家的任意两个城市都直接或间接的连通。为了省钱,每两个城市之间最多只能有一条直接的贸易路径。对于两个建立路线的方案,如果存在一个城市对,在两个方案中是否建立路线不一样,那么这两个方案就是不同的,否则就是相同的。现在你需要求出一共有多少不同的方案。

好了, 这就是困扰阿狸的问题。换句话说,你需要求出 \(n\) 个点的简单(无重边无自环)无向连通图数目。

由于这个数字可能非常大,你只需要输出方案数\(\mod 479 \times 2^{21} + 1\) 即可。

\(n \le 1.3 \times 10^5\)

这个题有一个多项式逆元做法但是不想讲

设n个点的简单无向连通图数目为 \(f_n\)

显然n个点的简单图有 \(2^{n \choose 2}\) 种

考虑0号节点所在的联通块,$ \sum_{i=1}^{n} \binom{n-1}{i-1} f_i\ 2^{\binom{n-i}{2}} = 2^{\binom{n}{2}} $

把 \(f_n\) 移到左边发现是一个卷积

然后每一个 \(f_n\) 都要算出 \(f_i\ (i < n) \)

然后考虑用 CDQ 分治的做法处理 \(f\)。\(solve(l,mid)\) 后对于已有的 \(f_i\ (l \le i < mid) \) 卷积,加入到 \(f_i\ (mid \le i < r) \)

时间复杂度 \(\Theta(n \log^2 n) \)

NOI2014 购票

今年夏天,NOI在SZ市迎来了她30周岁的生日。来自全国 \(n\) 个城市的OIer们都会从各地出发,到SZ市参加这次盛会。

全国的城市构成了一棵以SZ市为根的有根树,每个城市与它的父亲用道路连接。为了方便起见,我们将全国的 \(n\) 个城市用 \(1\) 到 \(n\) 的整数编号。其中SZ市的编号为 \(1\)。对于除SZ市之外的任意一个城市 \(v\),我们给出了它在这棵树上的父亲城市 \(f_v\) 以及到父亲城市道路的长度 \(s_v\)。

从城市 \(v\) 前往SZ市的方法为:选择城市 \(v\) 的一个祖先 \(a\)
,支付购票的费用,乘坐交通工具到达 \(a\)。再选择城市 \(a\) 的一个祖先 \(b\),支付费用并到达 \(b\)。以此类推,直至到达SZ市。

对于任意一个城市 \(v\),我们会给出一个交通工具的距离限制 \(l_v\)。对于城市 \(v\) 的祖先 \(a\),只有当它们之间所有道路的总长度不超过 \(l_v\) 时,从城市 \(v\) 才可以通过一次购票到达城市 \(a\),否则不能通过一次购票到达。对于每个城市 \(v\) ,我们还会给出两个非负整数 \(p_v\) 和 \(q_v\) 作为票价参数。若城市 \(v\) 到城市 \(a\) 所有道路的总长度为 \(d\),那么从城市 \(v\) 到城市 \(a\) 购买的票价为 \(d \times p_v + q_v\)。

每个城市的OIer都希望自己到达SZ市时,用于购票的总资金最少。你的任务就是,告诉每个城市的OIer他们所花的最少资金是多少。

\(n \le 2 \times 10^5,\ 0 \le p_v \le 10^6,\ 0 \le q_v \le 10^{12}
,\ 1 \le f_v < v,\ 0 < s_v \le l_v \le 2 \times 10^{11} \)

这个dp出来明显是一个下凸的,那么可以dfs的时候用可持久化数据结构维护凸壳然后在凸壳上二分,时间复杂度写得好应该是 \(\Theta(n \log^2 n) \)

然而有一种更巧妙的做法。考虑点分治,找出重心后先分治当前根所在的子树,然后用得到的值去更新其他子树。时间复杂度还是 \(\Theta(n \log^2 n) \)

而且更难写了(逃

整体二分

感觉没什么好说的啊

简单来说思想就是如果你对每一个询问二分,每次二分出来的值都要用线性时间来check

然而二分出来的值的个数是有限的,你可以把所有查询离线下来,然后对于当前要在某个值上check的很多询问一起check一次

如果CDQ分治是计算区间前一半对后一半的贡献,那整体二分就是用后一半的结果决定某些询问要不要进入前一半去计算

比如动态区间第k大

TO BE CONTINUED

本作品采用 CC BY-NC-SA 4.0 Unported License 进行许可
本文链接:https://dozbear.com/more-divide-and-conquer/