解决问题:
给定 \(n\) 个一次函数 \(y=k_ix_i+b_i\) 要支持一下操作:
- \(i\in [l,r],\;x_i\to x_i+p\)。
- \(i\in [l,r],\;b_i\to b_i+w\)。
- 查询 \(\max_{i=l}^{r} kx_i+b_i\)。
其中满足 \(p \ge 0\)。
发现如果只有 2,3 操作就是简单题了。
加上 1 操作的话就需要 KTT (Kinetic tournament tree) 来维护,KTT 就是线段树的一个变种。
1 操作不好维护的原因是因为每个位置增加的值不同,最大值位置可能发生改变,线段树每个节点在正常维护 \(l,r,mx\) 的基础上多维护一个 \(itr,b\) (交替阈值,区间最大值所取的函数所对斜率),表示这整个区间至少加多少后区间最大值位置会有变化,以这题为例 \(itr=\min\{ls_{itr},rs_{itr},\frac{ls_{mx}-rs_{mx}}{ls_{b}-rs_{b}}\}\) 线段树修改时,对于区间 \([l,r]\) 加 \(d\) 则让其 \(itr\to itr-d\)。若此时 \(itr\leq 0\) 则暴力将该子树所有标记下放直至遇到 \(itr>0\) 的节点。
时间复杂度在 EI 的文章 中有详细的讲解。
KTT 解决的问题需满足函数 \(x\) 增值均为正或均为负。
考虑几个问题:
旅行规划(弱化)
给定一个长为 \(n\) 的序列,支持两种操作:
- 区间加等差数列( \(a,a+p,a+2p\) )。
- 查询区间最大值。
其中保证等差数列中任意元素均大于 0。
让序列第 \(i\) 项 \(k_i=i\) 即可转化为第一个问题,每次操作拆分成:
\(i\in [l,r],\; x_i+p\)
\(i\in [l,r],\; b_i-(l-1)p\)
查询与第一个问题相同。
EI 的第六分块
给定一个长为 \(n\) 的序列,支持两种操作:
- 区间加。
- 查询区间最大子段和。
根据小白逛公园的思想,区间 \([l,r]\) 维护 \(lx,rx,mx\) 分别表示必须包含左或右端点的最大子段和,当前整个区间的最大子段和。
每个节点维护三个函数 \(y=kx+b\) 表示区间三种最大子段和,\(k\) 为三种最大子段和所对子段的长度。\(b\) 为三种最大子段和当前的和。\([l,r]\) 加 \(d\),相当于 \(x\to x+d\)。\(itr\) 要考虑三种最大子段和每一种的更新。
有一个需要注意,在取到最大子段和的前提下要使长度尽量长 (斜率越大增长越快)。
P6792 区间加
跟 EI 的第六分块基本一致,吉司机线段树 + KTT,把 EI 的第六分块中的 \(y=kx+b\) 的 \(k\) 改为最大子段和所对子段中包含区间最小值的个数即可。