Kinetic tournament tree 简称 KTT 下文中全部简写。
KTT 用于解决类以下问题：
- 已知 N N N 条一次函数，求解一段区间内函数最大值。
- 支持修改操作可以修改 x i x_i xi 或者 b i b_i bi 的值。
具体做法：
我们考虑线段树来维护一个类似 Δ \Delta Δ 的东西，我们令当前线段树区间 u u u 中函数值最大的线段是 y = k x + b y=kx+b y=kx+b 的，线段树还维护一个 t h r u thr_u thru 表示当前线段树节点下，如果讲 x i x_i xi 加超过 Δ \Delta Δ 这个最大值就会改变。
所以我们实际就是维护 t h r u thr_u thru 的东西。
首先，求当前区间中函数值最大值直接将两个儿子最大值取个 max \max max 即可，但是 Δ \Delta Δ 显然可以取到 min \min min 但是取到那些的 min \min min 呢，首先是 k = min ( t h r l s u , t h r r s u ) k=\min(thr_{ls_u},thr_{rs_u}) k=min(thrlsu,thrrsu) 然后就是 Δ u = min ( t , 两条线段的交点 ) \Delta u=\min(t,两条线段的交点) Δu=min(t,两条线段的交点) 因为这个时候肯定最大值会变。
然后修改的时候如果此时要加的值是 ≤ t h r u \le thr_u ≤thru 的那就最大值不会发生变化，否则把标记修改下传，势能分析得均摊 O ( log 3 n ) O(\log^3n) O(log3n) 的。
然后这就做完了基本操作。
[ROI 2018] Innophone
看到这个题，首先第一眼就是 ( a , b ) (a,b) (a,b) 肯定是原序列中某个 ( x i , y j ) (x_i,y_j) (xi,yj) 的组合，因为这样才不会浪费，就是可以把等于贡献算进去。
然后按照 X X X 为第一关键字排序，这样我们钦定 a = X i a=X_i a=Xi 那么这部分贡献就是 a × ( n − i + 1 ) a\times (n-i+1) a×(n−i+1) 然后考虑 i i i 前面的最大的 b = Y j b=Y_j b=Yj 满足 b × ( ∑ k = 1 i − 1 [ Y k ≥ Y j ] ) b\times (\sum_{k=1}^{i-1} [Y_k\ge Y_j]) b×(∑k=1i−1[Yk≥Yj]) 这个东西最大，然后显然这个东西形如 y = k × x y=k\times x y=k×x 并且 k k k 固定，每次加入一个 Y i Y_i Yi 只会让那些 k ∈ [ 1 , Y i ] k\in [1,Y_i] k∈[1,Yi] 的 x k x_k xk 加一，这是个类似权值线段树就能干的东西，我们按照 Y i Y_i Yi 从小到大的顺序来建线段树，然后直接前缀加，全局查找最大值，即可。
时间复杂度是 O ( n log 2 n ) O(n\log ^2n) O(nlog2n) 的但是显然跑不满。
代码
