KTT入门

Kinetic tournament tree 简称 KTT 下文中全部简写。

KTT 用于解决类以下问题：

1. 已知 $N$ 条一次函数，求解一段区间内函数最大值。
2. 支持修改操作可以修改 $x_i$ 或者 $b_i$ 的值。

具体做法：

我们考虑线段树来维护一个类似 $\Delta$ 的东西，我们令当前线段树区间 $u$ 中函数值最大的线段是 $y=kx+b$ 的，线段树还维护一个 $th{r}_u$ 表示当前线段树节点下，如果讲 $x_i$ 加超过 $\Delta$ 这个最大值就会改变。

所以我们实际就是维护 $th{r}_u$ 的东西。

首先，求当前区间中函数值最大值直接将两个儿子最大值取个 $\max$ 即可，但是 $\Delta$ 显然可以取到 $\min$ 但是取到那些的 $\min$ 呢，首先是 $k=\min (th{r}_{l{s}_u},th{r}_{r{s}_u})$ 然后就是 $\Delta u=\min (t,两条线段的交点)$ 因为这个时候肯定最大值会变。

然后修改的时候如果此时要加的值是 $\le th{r}_u$ 的那就最大值不会发生变化，否则把标记修改下传，势能分析得均摊 $O({\log }^{3}n)$ 的。

然后这就做完了基本操作。

[ROI 2018] Innophone

看到这个题，首先第一眼就是 $(a,b)$ 肯定是原序列中某个 $(x_i,y_j)$ 的组合，因为这样才不会浪费，就是可以把等于贡献算进去。

然后按照 $X$ 为第一关键字排序，这样我们钦定 $a=X_i$ 那么这部分贡献就是 $a\times (n-i+1)$ 然后考虑 $i$ 前面的最大的 $b=Y_j$ 满足 $b\times ({\sum }_{k=1}^{i-1}[Y_k\ge Y_j])$ 这个东西最大，然后显然这个东西形如 $y=k\times x$ 并且 $k$ 固定，每次加入一个 $Y_i$ 只会让那些 $k\in [1,Y_i]$ 的 $x_k$ 加一，这是个类似权值线段树就能干的东西，我们按照 $Y_i$ 从小到大的顺序来建线段树，然后直接前缀加，全局查找最大值，即可。

时间复杂度是 $O(n{\log }^{2}n)$ 的但是显然跑不满。

代码