Kinetic Tournament Tree 不详细揭秘

Luciylove · 2024-11-14 11:32:16 · 算法·理论

Preface

此处的复杂度分析貌似挺不正论的，可以看一下论文。

丢掉了一些我做不动的题目，大伙就当看个题就好了。

Question

题目的形式是：\forall i\in [1, n],f_i = k_ix_i + b_i，维护：

• 给定 l, r, v：\forall i \in [l, r] x_i = x_i + v (v > 0)。

• 给定 l, r 求：\max^{r}_{i = l} f_i(x_i)。

Theory

考虑对于每个节点维护一个目前最优的一次函数 f(x) 以及其被更换的阈值 \text{threshold}，简单记为 thr。

更换的阈值即使两个一次函数的交点，注意 0 的除法。

然后对于每次更改我们自底向上维护，然后节点的 thr 就是对左右儿子的 thr 取 min，并和 f_{lc}(x) 和 f_{rc}(x) 发生切换的 thr 取 min。

增加操作就直接如果 thr \geq v 那么直接加，对于每个 f(x) 由 b \to b + k \times v 即可，否则递归并进行维护。

查询操作就是每次直接算就好了这个是简易的。

我们发现这个切换函数是一个爬树的过程，考虑与树高进行相关定义。

考虑定义势能函数 \Phi = \sum_{v \in S} dep_v 其中 v \in S 即为潜在切换的集合。

每次的增加，会给 \log_n 个节点打上标记，子树内的标记显然是无关的。对于打标记的节点，其父亲可能被加入集合中，那么就是 \log n 的势能增加。

所以结合深度，单次的势能增加为 \Delta \Phi = \log^2 n。

那么 \log n 次递归必然将儿子换上父亲一次，\Delta\Phi \geq -1。

那么我们就可以用最多 \log^3 n 次来清空势能，所以时间复杂度为 m \log^3 n，m 是操作一的次数。

Problem

CF1178G The Awesomest Vertex

树上做 b 的根到点的链上前缀和，然后用 dfs 序来维护，套用模板即可。

P5693 EI 的第六分块

考虑最大子段和，是 lmx / rmx / sum / ans 的维护。

这个可以看做一次函数的相加。然后时间复杂度的证明可以看 EI 自己的证明，理论大致和之前相同。

然后就是自然的合并，Implement 可以参考下面的。

P6792 [SNOI2020] 区间和

考虑使用 Seg-beats 的理论维护，这两套势能系统是分开算的，然后就是普通的区间加，区间最大子段和了。

但是实现细节 / 复杂度证明较为复杂，建议观看题解实现。

CF1868F LIS?

考虑一直对一个最长的最大子段和加，然后让他换下去。

不难做到 \log^3 n，但是时限有五秒钟，可以通过！

P9288 [ROI 2018] Innophone

先将贡献写成如下形式方便理清思路：

注意到 x 的限制很大，所以我们考虑对 x 扫描线。

现在只需要有一个黑盒可以支持维护 y 轴的信息。

这等价于维护若干个正比例函数 y = bx，每次我们加入一个满足 a = x_i 的 y_i，需要对 [1, y_i] 的 x 平移 1 的位置，查询全局最大值。

由于维护的斜率是单调的，只有可能由斜率大的的换上来，而且这个切换是不可逆的，所以修改并不会增加势能，复杂度 O(n \log^2 n)。

有双倍经验 CF436F Banners。

P8987 [北大集训 2021] 简单数据结构

注意到操作本质上是区间竖线移位，一个点在 v_1 时刻被加入到了被 v checkmin 后的集合 T 之中，这有什么性质？

注意到这个集合 T 都满足 a_i 单调。

证明：

• 加入这个集合的时候，集合中小于他的数全部都 \leq x
• 这个时刻还没有加入这个集合的斜率小于他的数的值 \leq v，所以满足截距小于他，所以未来的值只会比他大。

注意到这个性质后，直接线段树二分+推平即可解决问题。

问题是如果没有呢？

考虑使用 KTT，每次取出最大值即可，注意斜率是单调的。只会换大的数上来。同时维护一套区间加、区间和即可。

复杂度 O((n + q) \log^2 n) 非常优秀。

P5073 [Ynoi2015] 世上最幸福的女孩

考虑按照 v_i 排序，然后变成正值全局加、区间最大子段和。

使用 KTT 维护即可过不了一点，理论复杂度正确！

但实际上做法应该是根据凸性，写闵可夫斯基和。

CF1830F The Third Grace

考虑记 f_i 为以 i 作为目前产生贡献处的答案。