5.1.3 [学习笔记]KTT 初步
有 \(n\) 个函数 \(f_i:\mathbb R\rightarrow \mathbb R\)，对于 \(x_1<x_2<\cdots <x_m\) 的每个 \(x_k\) 求
\[
\max_{j=1}^{n}\{f_j(x_k)\}
\]
询问的 \(x\) 单调递增。
考虑这样一种线段树：每个叶子表示了一个函数，每个节点维护两个信息
- 在当前 \(x\) 下取到最大值的函数是哪个
- 子树内每个节点取到最大值的函数第一次发生改变的时候的 \(x\) 的值。
当下一个询问超过这个 \(x\) 的时候，重构整个子树。
这个做法的好处是可以修改某一个函数。
复杂度证明：这我哪会啊，\(\mathcal O((n+q)\log^3 n)\) 说是。
CF1830F. The Third Grace¶
动理序列最值 · 弱化版
设 \(f_i\) 表示选取第 \(i\) 个点，但不计算这个点贡献的最大值。转移就是
\[
f_i=\max_{j=1}^{i-1}\{f_j+c_{j,i}p_j\}
\]
其中 \(c_{j,i}\) 是满足 \(i\notin[l,r],j\in [l,r]\) 的区间 \([l,r]\) 个数。
我们维护一个序列 \(\{a_i\}\)，其中 \(a_i=p_ix_i+f_i\)。
每次在转移完 \(f_i\) 后，对所有 \(r_j=i\) 的区间 \([l_j,r_j]\)，令区间内的 \(x_k\leftarrow x_k+1\)。