Kinetic Tournament Tree

考虑这样一个问题：\(n\) 个一次函数 \(k_i x_i + b_i\)，每个一次函数初始有 \(x_i = 0\)；区间对 \(x_i\) 加正数 \(x\)，区间查询 \(\max\limits_{i = l}^r k_i x_i + b_i\)。

考虑每个点维护当 \(x_i = 0\) 时值最大的函数，然后额外维护一个阈值 \(t\)，表示当 \(x\) 增大到 \(t\) 时这个点的子树中至少有一个的最大函数会发生改变。这个是很好维护的，pushup 的时候对两边儿子的 \(t\) 取个 \(\min\)，然后再算儿子的最大函数的交点横坐标（下取整）即可。

区间加就递归到 \(t \ge x\) 的子树然后打标记。给一次函数的 \(b_i\) 加上 \(k_i x\)，阈值减少 \(x\) 即可。

正确性比较显然。复杂度经过势能分析是 \(O(n \log^3 n)\) 级别的，但是实际运行跑得很不满。

1. P5693 EI 的第六分块

考虑沿用最大子段和的线段树维护方法，即一个点维护 \((pmx, smx, ans, sum)\)。

我们把它们都看成是一次函数，然后修改阈值 \(t\) 的定义为子树内的所有这些信息的最大函数第一次发生变化的最小需要加的 \(x\)。然后套 KTT 板子即可。

2. CF1178G The Awesomest Vertex

我们记 \(A_u = \sum\limits_{v \in R(u)} a_v, B_u = \sum\limits_{v \in R(u)} b_v\)，然后把子树拍平到序列。问题变为：

1. 区间对 \(A_i\) 加正数
2. 求 \(\max\limits_{i = l}^r |A_i| \times |B_u|\)

\(|B_u|\) 是固定的，所以可以预先取绝对值。考虑 \(|x| = \max(x, -x)\)，所以开两棵 KTT 维护即可（一个的 \(b_i\) 是 \(B_i\) 另一个是 \(-B_i\)）。

3. CF1830F The Third Grace

考虑 dp，设 \(f_i\) 为选第 \(i\) 个点的最大得分。这里为了方便，把第 \(i\) 个点的贡献放到往右边转移的时候再计算。

有 \(f_j = \max f_i + c_{i, j} p_i\)，其中 \(c_{i, j}\) 为 \(l \le i \le r < j\) 的区间数量。

考虑扫描线，扫右端点，同时 KTT 维护 \(f_i + c_{i, j} p_i\)，当 \(j \to j + 1\) 时把所有 \(r = j\) 的区间的 \([l, r]\) 的值加上 \(p_i\)。还要支持把单点修改成 \(f_i\)。套板子即可。

挺抽象的，\(O(n \log^3 n)\) 过 \(10^6\)。