分治和分块

分治

在当我们遇到一个数据范围很大的问题时,如果观察得到我们可以把它分解成几个更小的子问题,并且可以在线性时间中将两个子问题的答案合并,那么就可以考虑分治。

简单分治的例题有排序、平面最近点对(!!!)等。

树分治

树分治包含点分治、边分治、链分治,是用来解决一类关于树上路径的问题的算法。

点分治

首先选择一个点,将无根树变成有根树,再递归处理每一颗以根节点的儿子为根的树,然后统计。

为了使得递归层数尽量少,我们要选取原树的一个点,使得删除这个点后,剩下的联通块中最大的最小,我们称其为重心。每次处理子树时均选择重心作为分治起点,递归层数可以控制在\(\log n\)。

重心可以通过直接按照定义搜索求得。随便选一个根作为搜索起点,求出每个点的子树大小,每个点\(u\)的权值即为\(\max\{size_{v_{uk}},\cdots,n-size_u\}\),直接找到权值最小的点即可。

例题:IOI2011 Race

给定一颗\(n\)个点的有边权的树,求一条路径使得权值和为\(K\)并且边的数量最小。\(1\leq n\leq 10^5, K\leq 10^6\)

我们考虑某条路径在点分树中的表达方式,有两种:

  • 某一个点到子树根的路径。
  • 来自两个子树经过子树根的拼起来的路径。

总结来说就是一条以根为\(\text{LCA}\)的路径。我们设……

边分治

在树中选择一条边,递归砍断这条边后形成的两个子树,统计与这条边有关的信息。

与点分治相似,我们也要选择一条边使得两个子树尽可能小。可是,为了保持时间复杂度在\(\log n\)级别,每个点的度数要控制在3(菊花图直接卡成\(O(n)\))。这样可以通过加虚点和虚边来做到……

例题:BZOJ2870

给定一颗n个点的带边权的树,求树上的一条链使得链长和链最小值乘积最大。\(1\leq n\leq 100000\)

这里出现了两个不太相关的量,所以我们考虑固定一个值而求另外一个。考虑固定链最小值而求最小链长。

在处理一条边的两个子树时,对于一个子树的一个答案,另一个子树中有一个比最小值大于等于的后缀答案,用树状数组维护。

链分治

链分治把树分成许多重链,用线段树或平衡树来维护每一个重链的性质。树链剖分算是一种链分治。有许多名词:

  • 重儿子
  • 轻儿子
  • 重边
  • 轻边
  • 重链
  • 轻链

每次经过一条轻边到达新的一条重链时子树大小都至少会减半,进而从根节点到叶子节点最多会经过\(\log n\)条轻边,\(\log n\)条重链,每次查询的复杂度会比下面的线性数据结构多一个\(\log\)。

CDQ分治和整体二分

CDQ分治和整体二分都是离线算法。

CDQ分治

一般流程是:对于区间\([L,R]\),递归计算\([L,M]\)和\([M+1,R]\)的贡献,然后计算\([L,M]\)对\([M+1,R]\)的贡献,相加即为答案。

例题:二维偏序

对于一个按照第一维\(a\)排序的序列,把它分成两段递归返回后,

整体二分

整体二分顾名思义,是对所有询问一起二分。他解决的问题主要是询问一些条件在第几次修改之后能够满足。

例题:Meteors

二分答案,假设当前二分的区间是\([L,R]\),答案在区间中,线段树模拟修改,直接枚举验证查询。从左往右二分验证,每次修改只会进行一次。

三分

三分用来解决凸函数上最值的问题。例如:给定一个下凸函数\(f(x)\)(给定图像上两点连线,两点横坐标间的点都在连线下方),如何求\([L,R]\)上的最小值?

对于当前区间\([L,R]\)取三等分点\(M_1\)和\(M_2\),如果\(f(M_1)>f(M_2)\),则可以证明最小值不在\([L,M_1]\)之间,对于\([M_2,R]\)同理。这样每次操作后区间长度会变成原来的\(\frac{2}{3}\),这样在\(\log_{\frac{3}{2}}n\)的时间里就可以得到要求的近似解。

分块

将区间中连续x个元素分为一个块,对于区间操作,分为整块和边角两部分处理,时间复杂度为……

例题:区间加,区间求和……

莫队

对于无修改的题目,如果知道区间\([l,r]\)的答案可以快速算出

发表评论

电子邮件地址不会被公开。 必填项已用*标注