以下内容写作于 2024 年 4 月，后文相对时间以此为准。当时原本打算对 KTT 进行重新梳理写一篇介绍，这篇略显混乱的题解就放在学校内网里没对外公开，但到退役时那篇只写了一半就一直鸽着了，或许强基结束后可以重新捡起来写一写。

摘要：在线单 log 的 KTT 变种，似乎跑得比当前整体二分的同复杂度离线做法快，感觉没有什么新奇的 idea，可能已经有别人写过了。

下面的描述可能有点抽象，感觉最好对 KTT 有一定的了解，可以去看 EI 论文，赞美 EI！

题目描述

给定长度为 $n$ 的整数序列 $a$，$q$ 次操作：

1. 给定 $v \in \mathbb Z$，对 $i \in [1, n] \cap \mathbb N$ 执行 $a_i \leftarrow \min(a_i, v)$。
2. 对 $i \in [1, n] \cap \mathbb N$ 执行 $a_i \leftarrow a_i + i$。
3. 给定 $[l, r] \subseteq [1, n]$，求 $\sum_{i \in [l, r] \cap \mathbb N} a_i$。

$1 \leqslant n, q \leqslant 2 \times 10^5$，给定整数值均在 $[0, 10^{12}]$ 中。

题解

注意到取最小值操作，考虑 Segment Tree Beats。

发现操作二会使相同的最大值变为多个值，破坏势能分析。但随即容易发现由于均为全局修改，取最小值操作产生过影响的位置的值始终单调不降，因此自然地将元素根据是否被取最小值操作影响过分为两类，下面称未被影响为第一类，否则为第二类。每次操作一在第二类位置中会影响一个后缀。

对于操作一，若第一类位置的值均不超过 $v$ 则只对第二类位置进行操作，否则操作完子树内至少有一个第一类位置转化为第二类，类似 Segment Tree Beats 递归部分总复杂度 $\Theta(n \log n)$。对于第二类位置的操作，我们可以维护每个结点子树内最左侧的第二类位置及其值，可以快速判定一个结点的第二类位置是否均会被当前修改影响，类似线段树上二分的实现可以做到该部分单次操作总时间复杂度 $\Theta(\log n)$。

对于操作二，除了操作一中判定第一类位置均不超过 $v$ 一般使用的最大值外，均可使用懒标记方便地维护。

容易说明两类位置的区间和均容易维护，因此问题转化为了如何快速判定一个区间中当前所有第一类位置的值均不超过 $v$。

这个问题放在后面叙述，我们可以观察每次操作的影响并进一步利用修改为全局的性质对数据结构的算法过程通过一定的交换顺序进行整理，使其更方便实现，作为对上述内容的总结：

第一类位置的区间和容易通过树状数组维护，用线段树维护第二类位置，结点维护对应区间值减当前操作二次数乘下标的和、位置和、个数、最左侧的位置、上次赋值操作的时间与值（同时附带一个布尔量作为懒标记）。

对于操作一，使用线段树上二分对第二类位置进行后缀赋值，时间复杂度 $\Theta(\log n)$，当第一类位置最大值不低于 $v$ 则对树状数组和线段树进行单点修改将该位置从第一类改为第二类，总时间复杂度 $\Theta(n \log n)$。

对于操作二，无需进行操作。

对于操作三，直接在树状数组和线段树上进行查询即可，时间复杂度 $\Theta(\log n)$。

因此我们只需维护第一类位置的全局最大值及其位置即可，需要支持全局加下标，单点删除。

我们将问题抽象化如下：

对于函数族 $\mathcal F$，满足其中定义域 $D$ 与值域均相同，且定义域与值域上分别定义了全序关系 $\leqslant$，不妨设常函数 $- \infty$ 在 $\mathcal F$ 中，设 $g(\mathcal F)$ 为最小的 $k$ 满足 $\forall f_1, f_2 \in \mathcal F, \nexists x_0, x_1, \dots, x_{k+1} \in D, \forall i \in [1, k+1] \cap \mathbb N, (x_{i - 1} \leqslant x_i) \land (\operatorname{sgn}((f_1(x_{i - 1}) - f_2(x_{i - 1}))\cdot(f_1(x_i)-f_2(x_i))) = -1)$ 即最大变号次数。令 $\lambda_s(n)$ 为最大的 $m$ 满足存在序列 $(\sigma_1, \sigma_2, \dots, \sigma_m) \in ([1, n] \cap \mathbb N)^m$ 满足 $\forall i \in [2, m] \cap \mathbb N, \sigma_{i - 1} \neq \sigma_i$，且 $\forall x \neq y, \nexists (a_0, a_1, \dots, a_{s + 1}) \in S, \forall i \in [1, s + 1] \cap \mathbb N, \{a_{i - 1}, a_i\} = \{x, y\}$，其中 $S$ 为 $\sigma$ 的子序列构成的集合，即最长的不存在两个不同值交替出现的长度大于 $s$ 的子序列的序列长度。

注意到单点赋值可能导致一个位置在相同自变量时取得不同的值，为了方便后面的分析，设 $\operatorname{P} \mathcal F$ 中函数的定义域 $D' = D \times \mathbb N = \{(x, n) | x \in D, n \in \mathbb N\}$，对于 $(x_1, n_1), (x_2, n_2) \in D'$，$(x_1, n_1) \leqslant (x_2, n_2)$ 当且仅当 $(x_1 < x_2) \lor ((x_1 = x_2) \land (n_1 \leqslant n_2))$。令 $\operatorname{P} \mathcal F = \left\{\begin{cases}f(x)&((x, n) \leqslant r)\\ -\infty & ((x,n) > r)\end{cases} \middle| f(x) \in \mathcal F, r \in D'\right\}$。事实上，除了 $D$ 有最大值的一些特殊情况（如 $|D| = 1$），一般题目中扩展 $D$ 至 $D'$ 实际上对 $g(\operatorname{P} \mathcal F)$ 不造成影响。

根据 Micha Sharir 与 Pankaj K. Agarwal 的相关论文，有 $g(\operatorname{P} \mathcal F) \leqslant g(\mathcal F) + 1, \lambda_1(n) = n, \lambda_2(n) = 2 n - 1, \lambda_3(n) = 2 n \alpha(n) + O(n)$，对于常数 $s$，$\lambda_s(n)$ 关于 $n$ 是近乎线性的。更多相关内容也可以参见 EI 的 2020 年国家集训队论文《浅谈函数最值的动态维护》。

有满足上述条件的函数族 $\mathcal F$，其中 $g(\mathcal F)$ 为常数。满足对于 $f_1, f_2 \in \mathcal F, x_0 \in D$，可以在 $\Theta(A)$ 的时间复杂度内求出 $\operatorname{sgn}(f_1(x_0)-f_2(x_0))$，在 $\Theta(B)$ 的时间复杂度内求出 $h(f_1, f_2, x_0) = \min\{x \in D | \{-1, 1\} \subseteq \{\operatorname{sgn}(f_1(a) - f_2(a)) | a \in [x_0, x] \cap \mathbb N\}\}$ 与 $a \geqslant x_0$ 最小的满足值不为 $0$ 的 $\operatorname{sgn}(f_1(a) - f_2(a))$，满足 $A \leqslant B$。

给定 $n$ 个 $\mathcal F$ 中的函数 $f_1, f_2, \dots, f_n$，与自变量 $x \in D$，$q$ 次操作：

1. 单点删除：给定 $p \in [1, n] \cap \mathbb N$，执行 $f_p \leftarrow - \infty$。

2. 全局加自变量：给定 $x' \in D$ 满足 $x' \geqslant x$，执行 $x \leftarrow x'$。

3. 求区间最大值：给定 $[l, r] \subseteq [1, n]$，查询 $\max_{i \in [l, r] \cap \mathbb N} f_i(x)$。

在此题中 $n$ 与原先相同，$q$ 为原先的 $\Theta(n + q)$，$D$ 为 $[0, q] \cap \mathbb N$，$g(\operatorname{P} \mathcal F) = 2, A = B = 1$，查询区间为全局，可以 $\Theta(1)$ 进行函数求值。此外还有一些下面不会用到的性质如线段斜率不降（若不进行单点删除按原写法即可利用决策点的单调性证明复杂度为 $\Theta((n + q) \log n)$，进行单点删除后破坏分析且仅根据该性质不足以做到）。

为了方便叙述，对于 $f_1, f_2 \in \mathcal F, x_0 \in D$，若 $\forall x \in [x_0, +\infty) \cap D, f_1(x) = f_2(x)$ 则称两个函数一样优，否则 $\min\{x \in D | (x \geqslant x_0) \land (f_1(x) \neq f_2(x))\}$ 处更大的一者更优。在一些题目中，可能对相等情况的处理不那么方便，我们可以将某一互不相同的编号作为第二关键字比较，或者说将 $\mathcal F$ 中函数的值域改为原先值与编号的二元组，避免相同情况的出现，但注意复杂度相关 $g$ 值可能因此产生常数上的差异。（虽然可能由于出题人往往不卡满且理论复杂度相差不大，在 OI 中并没有多大的差距。）

我们对线段树每个结点维护对应区间中最优的函数 $f_1$ 与 $h(f_1, f_2, x)$，其中 $f_2$ 为另一个儿子的当前最优函数，$x$ 为当前自变量取值。可以在 $\Theta(B)$ 的时间复杂度内上传单个结点的信息，因此建树时间复杂度严格 $\Theta(n B)$。

查询时我们直接对定位的结点集中维护的函数取当前自变量最大的一者即可，单次时间复杂度严格 $\Theta(A \log n)$ 外加一次对最终求出函数在当前自变量求值的复杂度。

对于单点修改，我们可以递归到叶子进行暴力修改并上传信息，单次时间复杂度严格 $\Theta(B \log n)$。

我们观察一个结点维护信息的变化次数：维护的 $h$ 值变化当且仅当维护的对应区间中最优函数发生变化或者某个儿子维护的函数发生变化，因此我们只需考察最优函数发生变化的次数。我们考察两个函数最优者变化的最大次数，显然不超过 $g(\operatorname{P} \mathcal F)$，因此单个结点维护的最优函数变化次数小于 $\lambda_{g(\operatorname{P} \mathcal F)}(l)$，其中 $l$ 是对应区间中函数个数。因此在 $g(\operatorname{P} \mathcal F)$ 为常数时总变化次数不超过 $\Theta(\lambda_{g(\operatorname{P} \mathcal F)}(n) \log n)$。

观察原先的 KTT 实现，容易发现其相当于用线段树维护了子树中维护函数发生变化的首个时间，每次需用到维护函数的操作若子树内维护函数发生变化则暴力递归并修改，因此时间复杂度会再乘上递归的用时 $O(\log n)$，最坏情况下可以达到 $\Theta(\lambda_{g(\operatorname{P} \mathcal F)}(n) \log n (\log n + B))$。

事实上，若我们能维护一个值域为 $D$ 的堆，满足可以均摊 $\Theta(C)$ 插入或弹出堆顶，保证堆顶单调不降，则我们可以将每个结点以维护的 $h$ 为权值插入堆，显然一个结点维护的函数改变要么当前自变量 $x$ 超过了 $h$，要么存在儿子维护的函数改变。因此我们每次操作当堆顶不高于当前自变量 $x$ 时弹出堆顶并修改对应结点的信息，并向上上传信息直至第一个信息不变的祖先结点。

总时间复杂度 $\Theta(\lambda_{g(\operatorname{P} \mathcal F)}(n) (B + C) \log n + q_2 + q_3 A \log n)$。

我们考虑 $D = [l, l + |D|) \cap \mathbb Z$ 的情况，我们可以用桶在额外 $\Theta(|D|)$ 的时空代价下做到 $\Theta(C) = \Theta(1)$，可以用 bitset 加哈希表做到额外 $\Theta(|D| / w)$ 的时空，此外我们也可以用 vEB 树做到 $\Theta(C) = \Theta(\log \log |D|)$。

因此我们完成了这道 CTT 题的在线单 $\log$ 算法，参考代码，根据本题数据常数瓶颈似乎在第二类位置的处理上，而非 KTT。

总结与展望

大概是去年下半年初学 KTT 的时候从区间加自变量的复杂度证明中发现上传信息的次数要少一个 $\log$，然后与离线维护上包络线比较发现全局加自变量时复杂度瓶颈也只在递归，可以直接用 vEB 将一个 $\log$ 换成 $\log \log$，今年天波在 U 群里推这道题，然后做的时候自然地想到了 KTT，发现可以直接用桶。

容易发现上述方法也可以推广到动态开点的 KTT 上，只需对每个结点记录父亲即可，KTT 也没法进行持久化，不用关心 Path Copy 带来的父亲可能不唯一。

对于 KTT 做线段树合并的情况，如果只将 $\lambda_s(n)$ 视作黑盒，我只能证明不劣于启发式合并逐个插入，可能可以观察 $\lambda_s(n)$ 的证明通过设立势能函数做到复杂度不变。

对于自变量定义域较大的情况，与离线单 $\log$ 的做法进行对比，瓶颈在于离线维护上包络线的做法可以 $\Theta(1)$ 直接判定当前自变量是否会引起定位结点集中结点上包络线当前段编号的变化，而在线 KTT 做法需要对整个子树进行刷新，导致在线的 KTT 做法目前的写法实质上对 $\lambda_s(n) \log n$ 个变化点进行了排序，而离线维护上包络线的做法类似建堆仅使用了更少量的比较信息。能否类似地设计数据结构使得在线 KTT 做法在复杂度上完全不劣于离线维护上包络线？

对于区间加自变量的需求，该方法所需的优先队列变成了区间减非负值、取出 $< 0$ 的所有元素，似乎不能比线段树做到更好，因此该方法毫无作用。能否通过多叉线段树等手段对 $\Theta(\log^3 n)$ 与 $\Theta(\log n)$ 进行平衡，但似乎在 $\Theta(\log^3 n)$ 的两个操作内部就卡死了？