UOJ Logo immortalCO的博客

博客

关于 UOJ 现状的一些看法

2019-08-23 10:59:04 By immortalCO

更新于 8 月 26 日

时间又过了两天。现状如下:

  • 博客里的“早安”消失了,多了一篇封禁公告

管理员终于开始工作了。

更新于 8 月 24 日

时间已经过去几天,观察到的现状如下:

  • 这篇文章多了一些赞,而不是踩。证明了希望 UOJ 能活下去的用户还是有一定数量的。

  • NOI2019 的题目还是没有加上来。

  • 博客里的『早安』还安安静静地躺在那里,安然无恙。

  • 从上述现状可以推断,没有任何管理员看到了这篇文章。

因此,我在此建议所有用户立即备份自己提交在 UOJ 上的代码和写在 UOJ 上的博客,以应对随时可能到来的终焉之日。

不知道几周之后的《暂别》,管理员会以怎样的一种心态写下呢?

以下原文

2015 年 UOJ 刚创立不久的时候,UOJ 的题目还在保证质量的同时保持着更新;UR 还保持着每个月一场左右的频率,题目的质量也都非常高,甚至可以和 IOI 相比;日志里还都是各位大神的高质量题解、算法等介绍。当时的 UOJ 可以说是 OI 中最高水平的社区,可以类比当时的『知乎』的地位。

然而现在的 2019 年,UOJ 的情况又怎么样了呢?题目方面,就算是 CCF 官方的比赛,也要延迟好几个月才加上 OJ(直到我写下博客的 2019 年 8 月 23 日,NOI 2019 的题目还是没有加上 UOJ),甚至有的时候一场比赛只加了一道管理员自己的题(某省 OI);比赛已经好久没办过,之前一个月一次的 UR 变成了一年甚至两年一次,前两年 NOI 前举办的 UNR 今年居然也消失了;日志里充斥着各种没有意义的水、吐槽、博客广告甚至早安晚安(搞笑的是,在我发完这篇博客十分钟后,又有一篇『早安』发了出来),Hack 里充斥着各种 Hack A+B,而管理员似乎都熟视无睹;就连两台评测机效率不同导致的不公平现象,在 2016 年提到后至今似乎也没解决。现在的 UOJ,除了第一、二版的高质量 UR 题外,没有任何不可替代的地方。

造成今天这样的局面,最主要的原因还是管理员的懈怠。加题、办比赛、维护社区环境,这些都是管理员的责任。如果说没有好题的来源导致办比赛困难,起码加官方试题的工作也要及时完成一下吧?更别说维护社区环境这种和技术完全无关的任务。『没有金刚钻,别揽瓷器活。』如果对维护 OJ 没有足够的兴趣、不愿意付出哪怕加一道题、删一个水帖的时间,请不要占着这个管理员职位,让那些真正有精力、有能力的人来维护 UOJ。作为一个注册、关注 UOJ 4 年、且所有算法博文都放在且只放在 UOJ 博客上的用户,见证着 UOJ 世风日下的过程,这样的结果怎能不让我痛心。可能一些老用户看到这样的结果,但担心受到『你行你上』、『站着说话不腰疼』的评价而不愿意挺身而出,那就让我来做一个刺头、一个坏人、一个靶子吧。现在的 UOJ,是你们希望看到的样子吗?

按惯例,现在大概是管理员换届的时间。与其发一篇充满个人经历的感人《暂别》,不如好好选出下一届的管理员,至少选出愿意维护题目、维护社区环境的那些人,让《暂别》评论区中的『管理员辛苦了』名副其实。现在的管理员,请你们三思!

EOF

// 当然,在一些情况下,管理员根本不会看到这篇文章。这篇文章也会被无数的『踩』和谩骂的评论区充满,沉没在在历史的深渊中。这样,UOJ 的未来可能已经不难预料了。

NOIP2018 D2T3 题解 + 关于动态 DP 等科技的一些总结

2018-11-12 11:29:08 By immortalCO

利益无关:猫锟不是本题的命题猫。

算法一

最小权覆盖集 = 全集 - 最大权独立集

强制取点、不取点可以使用把权值改成正无穷或负无穷实现。

接下来就是经典的“动态最大权独立集”了,这题的题解在我之前博客有,洛谷上也可以提交。

$O(n\log n)$。

算法二

考虑修改的两个点 $a,b$ 构成这条链。

可以把操作看作是:先在这条链伸出去的每棵子树上 DP,最后再在这条链上 DP。

伸出去的子树以及链的中间的点和修改无关,因而可以整合起来高效处理,因为它们的转移是不受影响的;但是 $a$ 和 $b$ 的转移是受影响的,需要单独处理。

因此可以先预处理出每个子树的 DP 值,然后用倍增或树剖维护“从一个点往上按照通用规则 DP 到另一个点的结果”,这样只需要特殊处理修改的点,其他地方只需要直接倍增。

$O(n\log n)$。

算法三

如果不想写倍增,也可以写这样一个算法:把所有的询问放在一起处理。

也就是说,由于每条链中间的 DP 转移全部相同,因而我们可以批量地对所有需要进行这一转移的 DP 进行转移,从而加快速度。

这个算法虽然实现较容易,但理解较为困难,因而不再叙述。

$O(n\log n)$。

总结

本题的三个做法对应着动态 DP、虚树计算和整体 DP 的思想,体现了三个算法(在一定条件下)的等价性。

动态 DP $\Rightarrow$ 虚树计算:动态维护被修改的点构成的虚树(可能会增加复杂度);

虚树计算 $\Rightarrow$ 动态 DP:一个一个加入虚树中的点;

动态 DP $\Rightarrow$ 整体 DP:每个修改看作时间的区间,用线段树批量应用修改(不一定可行);

整体 DP $\Rightarrow$ 动态 DP:一个一个询问进行处理,依次加入对称差(可能会增加复杂度);

虚树计算 $\Rightarrow$ 整体 DP:按询问分组批量进行;

整体 DP $\Rightarrow$ 虚树计算:通过 整体 DP $\Rightarrow$ 动态 DP $\Rightarrow$ 虚树计算 进行转化(不一定可行)。

可以看出,动态 DP 和整体 DP 具有很强的适用面,都有各自才能解决的问题;而虚树计算的能力则是最弱的,常常可以等复杂度地转化为另外两者(一些例外是需要在虚树上点分治的问题)。

基于变换合并的树上动态 DP 的链分治算法 & SDOI2017 切树游戏(cut)解题报告

2017-05-22 12:53:03 By immortalCO

最近听说 SDOI2017 R2 某题可以用我论文中的“基于链的分治优化树上动态 DP”的方法 A 掉……我很开心啊……

因此我把这道题出到了校内训练中……

在出题之前,肯定是要去把这题先做一遍的……然后,我发现我弄出了一些新的东西……!

题意简述

给出一棵无根树 $T$,节点从 $1$ 到 $n$ 编号,点 $i$ 的权值为 $v_i$。定义一棵树的权值为树中所有点的权值异或起来的结果。

你想要在树上玩一个游戏。你会做 $m$ 次以下两种操作:

  • C x y:将 $v_x$ 修改为 $y$。
  • Q k:询问 $T$ 有多少棵非空的连通子树,满足这棵子树的权值为 $k$。输出模 $10007$。

数据范围:$n,m\le 30000$,$0\le v_i,y,k < 128$。

时空限制:2s、128MB。

算法讨论

如果只有一次询问,非常容易想到暴力 DP。先转有根树。在全局记录答案数组 $ans(k)$ 表示权值为 $k$ 的子树个数。对每个点 $i$ 记录 $f(i, k)$ 表示子树中深度最小的点为 $i$ 且子树权值为 $k$ 的连通子树个数。记录 $g(i, j, k)$ 表示子树中深度最小的点为 $i$ 且所有其他的节点都在 $i$ 的前 $j$ 个子节点的子树中的连通子树个数。那么我们就有以下方程(设 $Ch(i)$ 为 $i$ 的子节点列表):

  • $g(i, 0, k) = [k=v_i]$
  • $g(i, j, k) = \sum_{t=0}^{127} g(i,j-1,t)\times (f(Ch(i)_j, k\oplus t) + [k\oplus t = 0])$
  • $f(i, k) = g(i, |Ch(i)|, k)$
  • $ans(k) = \sum_{i=1}^n f(i, k)$

总时间复杂度为 $O(nm\times 128^2)$。

接下来可以注意到第 2 个式子是一个“异或卷积”的形式,不难想到使用 FWT 可以优化到 $O(128\log 128)$。然后注意到 FWT 之后,加法和乘法都可以直接按位相加,因此可以在一开始就将所有数组 FWT,运算过程中全部使用 FWT 之后的数组,最后再将 $ans( * ) $ 数组 FWT 回去即可。这样就可以去掉一个 $\log 128$。时间复杂度为 $O((n + \log 128)\times 128)$。

再接下来就是优化修改复杂度了。看过我论文或做过 BZOJ 4712 的同学容易想到使用链分治维护树上动态 DP。首先将树进行轻重链剖分,然后按照重链构成的树的顺序进行 DP。如果这样以后每一条重链上的转移可以高效维护、支持修改,那么每次修改点 $p$ 之后,我们就可以高效地更新点 $p$ 到根的 $O(\log n)$ 条重链的信息即可。

首先 $ans(k)$ 是全局变量,不好维护。那么可以不记录 $ans( * )$,而是记录 $h(i, k)$ 表示 $i$ 子树中的 $f(i, k)$ 的和,那么这样整个 DP 就有子树的阶段性了。

可以发现 $f(i, k)$ 就是先将 $g(i, 0, * )$ 和所有子节点 $p$ 的 $f(p, k ) + [k = 0]$ 全部卷积起来的值。即如果设 $F_i(z)$ 表示 $f(i, * )$ 这一数组的生成函数,那么可以得出 $$F_i(z) = z^{v_i}\prod_{p\in Ch(i)} (F_p(z) + z^0) $$ 这里的卷积定义为异或卷积。那么对于一条重链上的每一个点 $i$,我们只需要将 $i$ 的所有轻儿子 $lp$ 的 $F_{lp}(z) + z^0$ 全部卷积起来,这样就考虑了所有轻儿子的子树中的贡献,设这个卷积的结果为 $LF_i(z)$。同样对于每个点我们记录 $LH_i(z)$ 表示这个点的每个轻儿子的 $H_{lp}(z)$ 之和(这里 $H_i(z)$ 的定义类似 $F_i(z)$,只不过是对 $h(i, * )$ 定义的)。每个点的轻边的信息和可以用线段树维护来支持高效修改。

Claris 大神说这里信息可减因此不用线段树,但我觉得这里的 $LF_i(z)$ 的信息相减需要做除法,如果出现 10007 的倍数则没有逆元,无法相除,因此我仍然采用线段树维护。

注意到上述算法只要求我们能求出 $F_{重链顶}(z)$ 和 $H_{重链顶}(z)$,就可以维护父亲重链的信息或答案了。因此现在只需要考虑所有过当前重链的子树。在这里我们有如下两种截然不同的思路。

基于维护序列信息的算法

论文中提到的方法是转化为序列上的问题,然后使用线段树维护。由于连通子树和重链的交一定也是一段连续的链,那么我们显然就可以像最大子段和问题那样,记录 $D_{a,b}(z)$ 表示 $a=[$左端点在连通子树中$]$、$b=[$右端点在连通子树中$]$ 的方案数。这个算法将修改复杂度优化为 $O(128\log^2 n + 128\log 128)$,已经可以通过本题了。

但是这个算法有一定的问题:首先它具有较大的常数因子,运行时间较慢。其次,这个算法仍然利用了具体题目的性质——连通子树和重链的交还是链。而并非所有的题都有这样的性质。最后,由于要不重不漏地计数,代码细节繁多,十分难写。

基于变换合并的算法

对于一条重链,设重链上的点按深度从小到大排序后为 $p_1,p_2,...,p_c$,那么我们可以得出以下方程:

  • $F_{p_c}(z) = H_{p_c}(z) = z^{v_{p_c}}$ (因为 $p_c$ 没有子节点)
  • $F_{p_i}(z) = LP_{p_i}(z) \times (F_{p_{i+1}}(z) + z^0) \times {z^{v_{p_i}}}$
  • $H_{p_i}(z) = H_{p_{i+1}}(z) + F_{p_{i}}(z)$

而我们所需要求的只有 $F_{p_1}(z)$ 和 $H_{p_1}(z)$。

可以观察到上面这个式子中,向量 $\left(F_{p_{i+1}}(z), H_{p_{i+1}}(z), z^0\right)$ 是通过一个线性变换得到向量 $\left(F_{p_i}(z), H_{p_i}(z), z^0\right)$,具体地来说是右乘上这样一个矩阵:

$$M_i=\begin{pmatrix} LF_{p_i}{z}\times {z^{v_{p_i}}} & LF_{p_i}{z}\times {z^{v_{p_i}}} & 0 \\ 0 & 1 & 0 \\ LF_{p_i}{z}\times {z^{v_{p_i}}} & LH_ {p_i} + LF_{p_i}{z}\times {z^{v_{p_i}}} & 1 \end{pmatrix}$$

而矩阵乘法是满足结合律的,也就是说,我们只需要用线段树支持单点修改某个矩阵 $M_i$、维护矩阵的积,我们就可以高效地求出我们所需要的向量 $(F_{p_1}(z), H_{p_1}(z), 1)$。而这是容易做到的,因此这个算法是完全可行的。这样,这个算法也将修改复杂度优化为了 $O(128\log^2 n + 128\log 128)$,可以通过本题。

简单优化这个算法的常数。注意到形如 $$\begin{pmatrix} \underline{a} & \underline{b} & 0 \\ 0 & 1 & 0 \\ \underline{c} & \underline{d} & 1 \end{pmatrix}$$ 的矩阵乘法对这个形式封闭,因为 $$\begin{pmatrix} \underline{a_1} & \underline{b_1} & 0 \\ 0 & 1 & 0 \\ \underline{c_1} & \underline{d_1} & 1 \end{pmatrix} \times \begin{pmatrix} \underline{a_2} & \underline{b_2} & 0 \\ 0 & 1 & 0 \\ \underline{c_2} & \underline{d_2} & 1 \end{pmatrix} = \begin{pmatrix} \underline{a_1 a_2} & \underline{b_1 + a_1 b_2} & 0 \\ 0 & 1 & 0 \\ \underline{a_2 c_1 + c_2} & \underline{b_2 c_1 + d_1 + d_2} & 1 \end{pmatrix}$$

因此我们只需要对每个矩阵维护 $a,b,c,d$ 四个变量即可。同时可以直接用等号右边的形式来计算矩阵乘法,这样就只需要做 $4$ 次而不是 $27$ 次生成函数乘法了,常数大大减小了。

比较与扩展

这两个算法的时间复杂度相同,并且都可以扩展到询问某一个有根树子树的信息——只需要对那一条重链询问一下信息和/变换和即可。

我们来审视一下后一个算法。首先,这个算法基于的是直接对这个 DP 本身进行优化这样一种思想,而不是通过分析具体题目的性质进行处理,因此这种算法具有更高的通用性。其次,由于这个算法是直接对这个 DP 本身进行优化,因此正确性显然,细节也要少于论文中介绍的在区间中维护 $D_{a,b}(z)$ 信息的方法(维护 $D_{a,b}(z)$ 这个方法必须严格分类,因此细节繁多,常数也较大)。因此这个算法比前一个的算法更加优秀。

然而,事实上这个算法同样利用了题目的一些性质——这题是计数类问题,而且转移是线性变换,因此可以用矩阵来维护,而矩阵恰恰是一种可以合并的变换。那么对于其他的题目,是否也能用这种基于变换合并的算法呢?

BZOJ 4712 加强版(不保证修改不降)

这是一道在论文中有提到的题目。论文中介绍的算法正是一种基于标记合并的算法,其标记为 $trans_{a,b}(x)=\min(a, x+b)$ 并且对加法封闭。这个算法的常数十分优秀。

树上动态最大权独立集问题

这同样是一道在论文中有提到的题目。论文中介绍的是使用线段树维护序列上信息的方法。

考虑新的思路。记录 $f(i)$ 表示所有点都在 $i$ 子树中的最大权独立集的权值(以下简称答案),$g(i)$ 表示所有点都在 $i$ 子树中且独立集不包括点 $i$ 的答案;同样记录 $Lf(i)$、$Lg(i)$ 表示所有轻儿子的 $f(lp)$ 或 $g(lp)$ 的和

首先写出 $p_i$ 关于 $p_{i+1}$ 的转移:

  • $g(p_i) = Lf(p_i) + f(p_{i+1})$
  • $f(p_i) = \max(g(p_i), v_i + Lg(p_i) + g_(p_{i+1})$

考虑对这些 $g_{p_i}$、$f_{p_i}$ 定义新的加法和乘法运算:其中“加法” $a\oplus b$ 定义为 $\max(a, b)$、“乘法” $a\otimes b$ 定义为 $a+b$——根据加法分类、乘法分步的原理定义。那么转移方程可以写成这样:

  • $g(p_i) = Lf(p_i) \otimes f(p_{i+1})$
  • $f(p_i) = Lf(p_i) \otimes f(p_{i+1}) \oplus v_i \otimes Lg(p_i) \otimes g_(p_{i+1})$ // 这里将 $g(p_i)$ 代入了

这样,我们的转移就同样是“线性变换”,可以用矩阵来维护矩阵乘法了。算法的正确性可以用将这种新定义运算的矩阵乘法展开后证明,也可以将这种算法类比为 Floyd 求最短路来理解——它和 Floyd 的实现其实是一样的。

神奇的子图

这就是论文题……

首先考虑树上的算法。记录 $f(i, k)$ 表示所有点都在 $i$ 中且 $i$ 的点度为 $k$ 时的连通子图最大权值和,记录 $g(i)$ 表示 $i$ 子树中所有点 $j$ 的 $\max f(j, * )$。转移的时候,$f(i, * )$ 是对子节点跑重量为 $1$、价值为 $\max f(p, k < K )$ 的背包,同时更新 $g(i)$。

可以注意到,背包可以写成卷积的形式,而卷积可以写成矩阵乘法的形式,因此使用矩阵来表示变换是完全可行的。维护向量 $(f(p_i, 0), f(p_i,1), ..., f(p_i, k), g(p_i), 1)$,这样不难写出转移矩阵,就可以进行转移了。使用线段树维护即可做到和论文中相同的复杂度。同样,结合圆方树可以得到本题的另一个满分算法,复杂度相同。

这个算法的细节比原来的算法要少非常多,常数也小一些。

UOJ 268

终于不是论文中提到的题目了……

题意经过简化后变成这样:给出一棵树,每个点有 $a_i,b_i$ 两个权值,定义一条链 $(x, y)$ 的权值为链上所有点的 $a_i$ 加上 $b_{\mathrm{LCA}(x, y)}$。要求单点修改 $a_i$、链上修改 $b_i$(修改都是加一个数或减一个数),动态维护权值最大的链。

可以类比《神奇的子图》记录状态 $f(i, k\in\{0,1,2\})$、$g(i)$,意义和转移类似《神奇的子图》,只是 $f(i, * )$ 更新 $g(i)$ 时要加上 $b_i$。单点修改 $a_i$ 容易支持,考虑如何支持链上修改 $b_i$。不妨将 $b_i$ 差分,即设 $b'_i = b_i - b_{fa(i)}$,那么我们同样可以用 $b'_i$ 写出转移方程,并且链上修改变成了单点修改,易于维护。

转化为单点修改后,虽然要进行 $4$ 个节点的单点修改,但单点修改的常数小于链上修改,因此这个算法常数优于之前的算法。

神奇的简单路径

又是论文中的题了……

题意简述:给出一张图,保证每个点双 $\le 8$,每次修改点权,或询问两点之间最长简单路径,或询问全局最长简单路径。

如果只有全局最长简单路径,那么就是《神奇的子图》的弱化版。现在考虑第一个询问。这种询问相当于在圆方树上做链上询问。如果是暴力的话,那么就是沿着链一个一个点 DP 上来。这种链上的 DP 显然也可以写成变换的形式,那么我们也只需要维护这条链上的变换和即可,具体实现同样用矩阵,复杂度和原算法相同。

要注意的是一个一个 DP 上来时有向上的一段和向下的一段,因此线段树中维护矩阵的积时也要维护一正一反两种信息。

总结

基于变换合并的树上动态 DP 算法,完全地采用了对 DP 本身进行优化的思想,思路较于一般的树上动态 DP 算法思路更加直观、正确性更加显然。它不仅可以通用地解决之前所有的问题,还可以获得更小的思维难度、更小的代码难度和更快的运行速度,是论文中介绍的原算法的一个很大的改进。

当然,这个算法还有一些局限性。希望大家能和我分享关于这方面的研究,希望在我们的共同努力下能有更多更好的算法出现。

用无旋转 Treap 来写 LCT

2017-02-17 11:18:51 By immortalCO

之前本猫做 http://uoj.ac/problem/173 的时候,发现如果将 Treap 的 size 记为整棵子树(而非当前层)的大小,复杂度好像是对的。之前过不了好像是建树时的 push_up 次数常数过大,我就把初始化改成先不 push_up,建好之后再 push_up,直接用优化成线性;后面改成每次修改完之后才 push_up 后,操作次数就只剩三百多万了。

然后就想用 Treap 来写 LCT,看一看能不能达到同样是 $O(n\log n)$ 的复杂度。本猫用的是非旋转、无权值的 Treap,利用 splitmerge 来维护序列,在 merge 时以 size 作为概率决定哪一个点在上面。

以下以 http://uoj.ac/problem/3 题为例。

结构体

struct Node
{
    Node *p, *l, *r;    // p:为了方便,记录节点父亲;l、r:左右儿子
    int val, max;    // val:自己的权值;max:当前重链上的最大权值
    uint cnt, sum;    // cnt:这个点的所有轻边的子树大小 + 1;sum:当前子树的 cnt 之和
    bool rev;  // 翻转标记
}

为了保证复杂度,本猫采用了“LCT 维护子树大小”的做法,将 cntsum 维护成子树大小,并据此作为 Treap 的随机种子。

access

这是 LCT 的最基本的操作。伪代码如下:

access(node):
    p = node 所在的重链
    q = 空链
    while p != null:
        # 设 b 为 node 的轻儿子
        将 p 所在的重链从 node 处拆分为 a、b 两段(node 是 a 段的末尾)

        # 维护轻边子树大小之和
        node.cnt += b.sum - q.sum
        更新 p 使得其正确维护信息

        # 设 q 为 node 的重儿子
        p = 连接 a、q 
        更新 p 使得其正确维护信息

        # 下一步循环
        q = p
        node = q 的重链顶端的父亲
        p = node 所在的重链

那么我们就要支持对 Treap 进行从某一个点开始拆分以及合并两个 Treap。显然合并就是 merge 操作。我们只需要实现一个自下而上的 split 操作,循环即可实现。注意这些操作中都要维护好每个节点的父亲。

其他 make_rootlinkcut 操作都能利用上述操作实现(link 只需要设置重链父亲并维护 cntcut 需要一次 split)。

效果

提交为 http://uoj.ac/submission/129275 。感觉上速度挺正常的,不比 Splay 版的慢多少(吐槽:同样的代码连续提交两次使用时间差了 0.7s!)。

为了验证我们维护子树大小确实能欧化复杂度,修改 cnt 的维护方式(修改后为 $O(n\log^2n)$)再次提交为 http://uoj.ac/submission/129302 。慢了一倍以上。

但仍然无法查明其复杂度是否低于 $O(n\log^2n)$。

有啥用

可能可以持久化?(然而还要解决 access 拼接次数是均摊的问题……)

可能可以用其他重量平衡树(如旋转版的 Treap)代替这里的非旋转 Treap,能解决更多 SAM + LCT 的题,或更好的解决 BZOJ 4234,甚至出到子树询问和仙人掌上?(之前有过块链 LCT 做法)

一种高效处理无修改区间或树上询问的数据结构(附代码)

2016-11-02 19:45:47 By immortalCO

问题描述

给出一个某种元素的序列 $a_1,a_2,...,a_n$,要求进行 $m$ 次询问,每一次是询问一段区间 $[l,r]$ 的某种支持结合律和快速合并的信息,要求在线。

这类问题比较通用,比如在 DP 的优化中就常常见到。

要求复杂度尽量优秀,假设合并复杂度为 $O(1)$。

以下的时间复杂度 $O(A) + O(B) + O(C)$ 表示预处理复杂度、单次询问的复杂度和空间复杂度。

各种性质的具体问题

可减信息,如区间和、区间异或和

直接用前缀和实现,复杂度 $O(n)+O(1)+O(n)$。

可重复贡献信息,如区间最值

如果序列很长,使用线段树即可,复杂度 $O(n)+O(\log n)+O(n)$。

如果询问很多,但序列不是特别长,可以用倍增的 RMQ,复杂度 $O(n\log n)+O(1) + O(n\log n)$。

如果序列很长,询问也很多,可以对序列线性建立笛卡尔树转为 LCA 问题,然后转为正负 1 RMQ,每 $\log n$ 分一段打表预处理,复杂度 $O(n)+O(1)+O(n)$。

仅满足支持结合律和快速合并,如最大子段和、区间的串哈希值

一般使用线段树实现,复杂度 $O(n) + O(\log n) + O(n)$。

一种新的做法

上面一般做法的问题是:询问复杂度不够优秀。

如果问题没有任何性质,一般只能使用线段树。然而在实际的问题(或所优化的问题)中,由于询问不受空间大小的限制,一般询问的次数是大大多于序列的长度的,比如有的莫队需要查询 $O(n\sqrt n)$ 次的区间最值,这样倍增 RMQ 就有了用武之地。因此,我们考虑能否像 RMQ 那样,在一般的问题上,以预处理的时间和空间,换取快速的询问

考虑一个询问 $[l,r]$。如果 $l=r$,则我们可以直接得出答案。否则,考虑 $[l,r]$ 在线段树上定位时,是在哪个线段树节点 $p$ 中同时递归到左右两个儿子(如果 $[l,r]$ 只定位为线段树上的一个节点,则视为同时递归进入两个儿子)。设该节点的区间 $[s, t)$,其中点为 $m$(两个一半的区间是 $[s,m)$ 和 $[m,t)$),那么区间一定是满足 $s\le l < m \le r < t$。如果我们对于每个 $l\le i < m$ 都预处理了 $[i,m)$ 的信息和 $prel(p,i)$,对于每个 $m \le i < r$ 都预处理了 $[m,i]$ 的信息和 $prer(p,i)$,那么所求的信息和就是 $prel(p,l)+prer(p,r)$。这一步是 $O(1)$ 的。现在唯一的问题是我们能否快速求出 $p$。

一般的线段树没有什么好的性质,但如果一棵线段树的值域是 $[0, 2^k-1)$,并且编号遵从堆式存储($i$ 的儿子为 $2i$ 和 $2i+1$),那么 $[l,r]$ 所定位的区间,就是 $[l,r]$ 所对应的两个节点的 LCA,也就是 $l,r$ 两个位置对应节点的编号的二进制数的 LCP!获得 $x,y$ 的二进制数的 LCP 只需要使用 x >> Log2[x ^ y](找出并丢弃第一个不同的二进制位及后面的位),其中 Log2 数组可以线性预处理,因此求出 $p$ 也只需要 $O(1)$ 的时间。这样,我们就得到了一种 $O(n\log n)+O(1)+O(n\log n)$ 的优秀算法。

我们称这一数据结构为猫树

应用

经典问题:区间最大子段和

给出一个序列,多次询问区间的最大子段和。

这是一个经典的模型。不同于经典做法,我们只需要记录 $prel$、$prer$ 为对应前(后)缀的最大子段和、最大前(后)缀和即可。

复杂度:$O(n\log n)+O(1)+O(n\log n)$。实测在 $n=m=200000,a_i\le 10^9$ 的情况下,此做法的运行时间接近经典做法(非递归线段树实现)的 $2\over 3$。

经典问题:NAND

给出一个序列,多次询问一个 $x$ 对一个区间中所有数按顺序依次 NAND 的结果。

NAND 没有结合律,因此我们要用一些经典的处理方式。NAND 是按位独立的,因此我们可以对每一位维护信息:如果这一位刚开始是 0,那么按顺序 NAND 了这个区间中的所有数后会变成什么;如果这一位是 1 那么会变成多少。用位运算可以优化为 $O(1)$ 的信息合并。

使用猫树,即可直接支持 $O(n\log n)+O(1)+O(n\log n)$。

经典问题:区间凸包

现在来看看不那么傻逼的题。

给出一个平面上的点的序列,每次询问一个区间的凸包的面积,保证横坐标单调递增,强制在线。

这题的凸包不是贡献独立的,因此我们必须求出这个凸包。经典做法是用线段树套可持久化平衡树维护凸包,在线段树的节点直接保存凸包,用可持久化线段树的合并保证复杂度,代码非常繁琐,复杂度为 $O(n \log^2n)+O(\log^2n)+O(n\log^2n)$。

结合猫树,只要我们可持久化地保存 $prel,prer$ 为区间的凸包,这样我们就只需要资磁对左右两边预处理的凸包二分出一个公切线,然后进行计算即可,并不需要直接合并两个平衡树维护的凸包。而这里的凸包由于只有 $x$ 单调的插入,用简单的可持久化数组(线段树或平衡树)即可直接维护,代码量很小。复杂度为 $O(n\log^2n)+O(\log n)+O(n\log^2n)$。

BZOJ4540

给出一个区间,每次询问一个区间 $[l,r]$ 的所有子区间的区间最小值之和。

根据猫树的思想,我们考虑分开来计算代价。其中,$[l,m)$ 和 $[m,r]$ 的答案可以用单调栈线性预处理,就只需要考虑跨越部分了。对 $[l,m)$ 中记录每个数到 $m$ 的区间最小值,考虑这个最小值贡献答案的区间的右端点 $r$,这个最右的右端点可以通过左右的归并得出。这样预处理之后,就能做到 $O(1)$ 的询问复杂度。这里的细节比较繁琐,不过多说明。

这个做法实际运行时间十分优秀,在 $n=100000,m=2\times 10^7$ 的数据可以 $0.3s$ 出解。

扩展?

优化 DP

如果某种 DP 需要按顺序决定,但有很多次的区间查询,我们可以用猫树结合二进制分组做到相同的复杂度。

在查询次数很多的情况下,此做法比直接线段树维护具有优势。

树上无修改询问

考虑把猫树扩展到树上,以资磁快速的链上信息询问。我们对树进行点分治,预处理所有点到重心的信息(需要保存“包括中心”和“不包括重心”两种信息,如果有方向要求要专门考虑),这样同样能拆成两个已经预处理的信息的和。

询问的时候,我们需要找出这条链上最上面的重心。对点分治建立点分树(把重心连成树),然后我们要找到的重心就是询问的链端点的 LCA,这可以用倍增 RMQ 来预处理。

复杂度和区间问题相同,$O(n\log n)+O(1)+O(n\log n)$。

其实 BZOJ4568 是这种做法的离线版本。

UPD:代码参考

区间最大子段和
    const int MaxN = 200010;
    const ll inf = 1000000000000000000ll;
    int val[MaxN], pos[MaxN];
    struct Node
    {
        struct Data {ll pre, sum;} *dl, *dr;
        int mov_l, mov_r;
        IL ll query(RG int l, RG int r)
        {
            return dl[l -= mov_l].sum > dr[r -= mov_r].sum 
                ? dmax(dl[l].sum, dl[l].pre + dr[r].pre)
                : dmax(dr[r].sum, dl[l].pre + dr[r].pre);
        }
    } T[524288];
    int N;
    void build(RG int i, RG int l, RG int r)
    {
        if(l + 1 == r || N <= l) return;
        RG int m = (l + r) >> 1;
        build(i << 1, l, m);
        build(i << 1 | 1, m, r);

        RG Node *o = T + i;
        o->dl = new Node::Data[m - l], o->mov_l = l;
        o->dr = new Node::Data[r - m], o->mov_r = m;
        RG ll pre, max_pre, sum, max_sum;
        pre = sum = 0, max_pre = max_sum = -inf;
        for(RG int k = m - 1; k >= l; --k)
        {
            pre += val[k],                     cmax(max_pre, pre);
            sum = dmax(sum, 0) + val[k],    cmax(max_sum, sum);
            o->dl[k - l] = (Node::Data) {max_pre, max_sum};
        }
        pre = sum = 0, max_pre = max_sum = -inf;
        for(RG int k = m; k <= r - 1; ++k)
        {
            pre += val[k],                     cmax(max_pre, pre);
            sum = dmax(sum, 0) + val[k],    cmax(max_sum, sum);
            o->dr[k - m] = (Node::Data) {max_pre, max_sum};
        }
    }
    int pre[1024];

    IL void main()
    {
        RG int (*F)() = read<int>;
        RG int n = N = F();
        Rep(i, 0, n) val[i] = F();
        RG int D = 1; while(D < n) D <<= 1;
        build(1, 0, D);
        RG int l, r, d, v;
        pre[0] = 0;
        Rep(i, 1, 1024) pre[i] = pre[i >> 1] + 1;
        Rep(_, 0, F())
        {
            l = F() - 1, r = F() - 1;
            if(l == r) Print(val[l]);
            else
            {
                l += D, r += D;
                v = l ^ r;
                d = (v < 1024 ? pre[v] : 10 + pre[v >> 10]);
                Print(T[l >> d].query(l - D, r - D));
            }
        }
        io::flush();
    }
BZOJ4540
    const int MaxN = 131072;
    int a[MaxN], N;
    // 对单调栈中的数进行归并,并确定每一位对应的单调栈中元素
    struct Node
    {
        int m;
        struct Data
        {
            int pos;            // 在左右单调栈中的排名
            ll sum, ans;        // 答案的和
            ll pre;                // 到中点这一段的和
        } *pre;
        IL ll query(RG int l, RG int r)
        {
            RG int pl = pre[l].pos, pr = pre[r].pos;
            return pre[l].pre + pre[r].pre + ((pl < pr)
                ? pre[l].ans + (m - l)       * (pre[r].sum - (pl == m - l        ? 0 : pre[l + pl - 1].sum))
                : pre[r].ans + (r - m + 1) * (pre[l].sum - (pr == r - m + 1 ? 0 : pre[r - pr + 1].sum)));
        }
    } T[262144];
    void build(RG const int i, RG const int l, RG const int r)
    {
        if(l + 1 == r || N <= l) return;
        RG const int m = T[i].m = (l + r) >> 1;
        build(i << 1, l, m);
        build(i << 1 | 1, m, r);

        RG Node::Data *f = T[i].pre = (new Node::Data[r - l]) - l;

        static int stack[MaxN], b[MaxN];
        RG int top, cur, V; RG ll pre, ran, sum;
        pre = sum = top = ran = 0; cur = 2000000000; *stack = m;
        for(RG int i = m - 1; i >= l; --i)
        {
            V = a[i];
            for(; top && a[stack[top]] >= V; --top)
                ran -= (ll) a[stack[top]] * (stack[top - 1] - stack[top]);
            ran += (ll) V * (stack[top] - i);
            stack[++top] = i;
            cmin(cur, V); 
            f[i].sum = (sum += (b[i] = cur));
            f[i].pre = (pre += ran);
        }
        pre = sum = top = ran = 0; cur = 2000000000; *stack = m - 1;
        for(RG int i = m; i <= r - 1; ++i)
        {
            V = a[i];
            for(; top && a[stack[top]] >= V; --top)
                ran -= (ll) a[stack[top]] * (stack[top] - stack[top - 1]);
            ran += (ll) V * (i - stack[top]);
            stack[++top] = i;
            cmin(cur, V);
            f[i].sum = (sum += b[i] = cur);
            f[i].pre = (pre += ran);
        }
        sum = 0;
        RG int pl = m - 1, pr = m, N = 0, tmp;
        while(l <= pl || pr < r)
            (pr >= r || (l <= pl && b[pl] > b[pr]))
                ? (f[pl].pos = ++N, (tmp = (N - (m - pl)))         ? sum += (ll) b[pl] * tmp : 0, f[pl--].ans = sum)
                : (f[pr].pos = ++N, (tmp = (N - (pr - m + 1)))     ? sum += (ll) b[pr] * tmp : 0, f[pr++].ans = sum);
    }

    IL void main()
    {
        RG int (*F)() = read<int>;
        RG int n = N = F(), m = F(), D = 1;
        while(D < n) D <<= 1;
        Rep(i, 0, n) a[i] = F();
        build(1, 0, D);
        RG int l, r, v, d;
        static int pre[1024];
        Rep(i, 1, 1024) pre[i] = pre[i >> 1] + 1;
        while(m--)
        {
            l = F() - 1, r = F() - 1;
            if(l == r) Print(a[l]);
            else
            {
                l += D, r += D;
                v = l ^ r;
                d = (v < 1024 ? pre[v] : 10 + pre[v >> 10]);
                Print(T[l >> d].query(l - D, r - D));
            }
        }
        io::flush();
    }
代码的模板
//pb_ds 20160711
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cassert>
#include <cmath>
#include <iostream>
using namespace std;
#define RG register
#define IL __inline__ __attribute__((always_inline))
#define For(i, a, b) for(RG int i = a, ___u = b; i <= ___u; ++i)
#define Dor(i, a, b) for(RG int i = b, ___d = a; i >= ___d; --i)
#define Rep(i, a, b) for(RG int i = a, ___u = b; i != ___u; ++i)
#define dmin(a, b) ((a) < (b) ? (a) : (b))
#define dmax(a, b) ((a) > (b) ? (a) : (b))
#define cmin(a, b) ((a) > (b) ? (a) = (b) : 1)
#define cmax(a, b) ((a) < (b) ? (a) = (b) : 1)
#define ddel(a, b) ((a) > (b) ? (a) - (b) : (b) - (a))
#define dabs(i) ((i) > 0 ? (i) : -(i))
typedef long long ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef long double ld;

#include <queue>
#include <vector>

namespace pb_ds
{   
    // 输入输出优化模板从此开始
    namespace io
    {
        const int MaxBuff = 1 << 15;
        const int Output = 1 << 23;
        char B[MaxBuff], *S = B, *T = B;
        //#define getc() getchar()
        #define getc() ((S == T) && (T = (S = B) + fread(B, 1, MaxBuff, stdin), S == T) ? 0 : *S++)
        char Out[Output], *iter = Out;
        IL void flush()
        {
            fwrite(Out, 1, iter - Out, stdout);
            iter = Out;
        }
    }

    template<class Type> IL Type read()
    {
        using namespace io;
        RG char ch; RG Type ans = 0; RG bool neg = 0;
        while(ch = getc(), (ch < '0' || ch > '9') && ch != '-')     ;
        ch == '-' ? neg = 1 : ans = ch - '0';
        while(ch = getc(), '0' <= ch && ch <= '9') ans = ans * 10 + ch - '0';
        return neg ? -ans : ans;
    }
    template<class Type> IL void Print(RG Type x, RG char ch = '\n')
    {
        using namespace io;
        if(!x) *iter++ = '0';
        else
        {
            if(x < 0) *iter++ = '-', x = -x;
            static int s[100]; RG int t = 0;
            while(x) s[++t] = x % 10, x /= 10;
            while(t) *iter++ = '0' + s[t--];
        }
        *iter++ = ch;
    }
    // 输入输出优化模板到此结束

    /** 把上面的代码拷贝到这里即可运行 */
    /** 把上面的代码拷贝到这里即可运行 */
    /** 把上面的代码拷贝到这里即可运行 */
    /** 把上面的代码拷贝到这里即可运行 */
    /** 把上面的代码拷贝到这里即可运行 */
    /** 把上面的代码拷贝到这里即可运行 */
}

int main()
{
    #define FILE "dev"
    //freopen(FILE ".in", "r", stdin), freopen(FILE ".out", "w", stdout);
    pb_ds::main();
    fclose(stdin), fclose(stdout);  
}

完结撒花

immortalCO Avatar