KTT
NahX_
·
·
算法·理论
解决问题：
给定 n 个一次函数 y=k_ix_i+b_i 要支持一下操作：
-
-
- 查询 \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 改为最大子段和所对子段中包含区间最小值的个数即可。