随了一个题(snoi2020 区间和)，然后看了一眼题解，感觉像是ktt?就来学了。
EI队长《浅谈函数最值的动态维护》的学习笔记。
引入
问题是，你需要维护平面上的一些函数，每次查询这些函数与一条竖线的最高交点，或者说给每个函数代入\(x\)，求其中最大的。
直线的情况是经典的，它就是个上凸壳。有结论说明，如果任意两个函数交点只有常数个，那么\(n\)个函数的上包络线(就是每个点所有函数取\(\max\))的段数几乎是线性的。
如果任意两个函数最多有\(s\)个交点，现在一共有\(n\)个函数，那么段数的上限记作\(\lambda_s(n)\)，当\(s=O(1)\)的时候它几乎是线性的(带几个\(\alpha\)，并且一般不会卡满)，但是当\(s\)很大的时候它好像是\(\alpha(n)\)为底的指数级。经典结论是，函数定义在区间上，它的\(s\)是定义在全局上的\(s\)加上\(2\)，原因是在区间端点可能产生拐点。
认为求交点和求值都是\(O(1)\)的。
分治
静态的\(n\)个函数，\(q\)次查询。
直接分治，然后归并，复杂度\(O(\lambda_s(n)\log n+q\log n)\)。
二进制分组
一边插入一边查询。
二进制分组是分治的不完全执行。分散层叠一下，合并的时候归并分散层叠，复杂度就和分治一样了。
KTT(烤兔兔)
保证查询的\(x\)单增，同时有\(m\)次修改操作，每次改一个函数。
先考虑没有修改怎么做。
考虑在函数序列上建一个线段树(虽然本来是集合，我们可以强行把它排成序列)，每个点维护区间内在现在要查询的\(x\)上值最大的函数\(f\)。我们再每个点维护一下\(x\)最小增加到多少，子树里的某个\(f\)就会切换到新的\(f\)，出现这样的事情就强行递归下去修改，然后合并上来。每个点的分段数是\(\lambda_s(len)\)，总共就是\(O(\lambda_s(n)\log n)\)，每次强行修改的代价是\(O(\log n)\)，总复杂度就是\(O(\lambda_s(n)\log^2 n+q)\)。好像也不是特别优（
然后如果有修改，我们直接改即可。但是这样会影响均摊，需要重新分析一下。
注意到这相当于每个函数出现在一个时间区间上，而\(x\)单增是说查询的值就是时间，于是每个函数就是一个区间上的分段函数，它的总复杂度就是\(O(\lambda_{s+2}(n+m)\log^2 n+q)\)。
核心就是维护下一次切换的时间。
KTT和一些一次函数的问题
我只能说牛逼。可以说是最困难的一类均摊线段树。
经典问题。
给两个序列\(k,b\)，支持
-
给一个区间和\(x>0\)，把区间内的\(b_i\)加上\(k_ix\)
-
给一个区间和\(c>0,x,y\)，把区间内的\(k_i\)变成\(ck_i+x\)，\(b_i\)变成\(cb_i+y\)
-
查询\(b\)的区间\(\max\)
。复杂度3\(\log\)。
你发现每个位置是一个一次函数，每个一次函数有一个\(x\)，第一个操作和查询就是区间\(x\)加正数和区间查询；第二个操作是对这个一次函数序列有两个系数的区间加和区间乘。
考虑怎么ktt。首先\(x\)加正数是简单的，因为 下一次切换需要加到多少 是可以快速合并的。
然后你发现第二个操作居然不影响覆盖的点的切换，也就是说原来两个一次函数\(k_1x+b_1,k_2x+b_2\)会在\(-\frac{b_1-b_2}{k_1-k_2}\)这个位置发生切换，现在完全没变。
但是尽管这个东西不影响覆盖的点，还是会影响内外之间的，从而破坏均摊。接下来我们把它分析到3\(\log\)。
考虑因为我们的\(x\)单增，发生切换的时候一定是从斜率小的换到斜率大的。考虑一次切换之后会发生什么，这个点从斜率较小的儿子转向了斜率较大的儿子，那么它的斜率就变大了，从而让它的父亲有可能再转向它。
考虑所有选择斜率较小儿子的点，令势函数是这些点的深度和，那么每次一个点切换之后，最多只会影响它的父亲，于是势能会减少至少\(1\)。
两种操作都只会影响\(\log\)个结点，于是它们都只会增加最多\(\log^2\)的势能，一开始还有\(O(n\log n)\)的势能。于是总共有\(O(n\log n+m\log^2 n)\)的势能，也就是最多发生这么多次切换，每次是\(O(\log n)\)的，最后总复杂度就是\(O(n\log^2 n+m\log^3 n+q\log n)\)。
它看起来很高，但是1e5随便跑，因为很不满。
区间加公差为正数的等差数列，区间\(\max\)
这个相当于没有第二个操作，并且\(k_i=i\)。
由于\(k\)是单调的，每次切换必然是从左儿子到右儿子，此时每个点只会发生一次切换，复杂度就会少一个\(\log\)。
CF1178G The Awesomest Vertex
给一棵树，每个点有两个权值\(a_u,b_u\)，权值可能是负的。定义一个点的牛逼值是它祖先们(包括自己)\(a\)之和的绝对值和\(b\)之和的绝对值的乘积，要支持给一个点的\(a\)加正数，求子树最大牛逼值。\(n\leq 2\times 10^5,q\leq 10^5\)。
你发现这看起来很像是凸壳!这相当于是把一堆向量加起来，然后求两维绝对值乘积的最大值。然而你发现最小值才是凸壳。
修改是给子树里每个向量横着平移。对四个象限分开，爆力处理象限变化的情况，你发现这种事情只会发生\(O(n)\)次。然后子树是dfn上的区间，问题变成区间给\(a_i\)加一个数，求区间\(a_ib_i\)的最小/大值。直接ktt维护即可，复杂度是三个\(\log\)。
CF573E Bear and Bowling
给一个可能有负数的序列\(a\)，求一个子序列\(b\)，最大化\(\sum_{i}ib_i\)。\(n\leq 10^5\)。
考虑一个dp，设\(dp(i,j)\)表示最后一个是\(i\)，长度为\(k\)的子序列的答案，那么转移就是\(dp(i,j)=ja_i+\max\limits_k dp(k,j-1)\)。
进行一个结论的猜，这个东西是决策单调的，于是可以导出平衡树优化差分数组的牛逼1\(\log\)做法。
另一个牛逼做法是考虑贪心，我们从空开始，每次选使得新的答案最大的那个数加入子序列，并更新答案。如果是在场上，你可以拍一拍来说明它是对的（
于是就简单了，选一个数\(a_i\)的贡献，假设它左边有\(k\)个被选了的，它右边被选了的和是\(s\)，那么贡献就是\((k+1)a_i+s\)。于是我们要支持全局\(\max\)，后缀的\(k\)加上\(1\)，前缀的\(s\)加上\(a_i\)。直接ktt即可。
但是这题可以1\(\log\)啊?我们还是来学习一下，不过学习之前先咕咕咕。
ROI 2018 Day1 T3 Innophone
有一堆二元组\((x,y)\)，并且\(y\leq x\)。你可以选择常数\(a,b\)，然后\((x,y)\)的贡献会是
-
如果\(a\leq x\)，那么是\(a\)
-
否则，如果\(b\leq y\)，那么是\(b\)
-
否则，是\(0\)
，最大化贡献的和。\(n\leq 1.5\times 10^5,0\leq y\leq x\leq 10^9\)。
显然\(a\)在某个\(x\)处最优，\(b\)在某个\(y\)处最优。我们从小到大枚举一个\(a\)，那么\(b\)所要考虑的二元组数量每次都会增加，假设这些\(y\)排序之后依次是\(t_1,...,t_m\)，\(b\)所要最大化的形式大概是\((m-i)t_i\)。操作会是斜率的区间加，ktt冲就行了。
TB6
区间加正数，区间最大子段和。
最大前/后缀和是两个东西的\(\max\)，子段是三个。强行维护切换，可以分析到3\(\log\)。
核心在于设计一个势函数，使得切换总是会消耗势能。还是只会从斜率小的切换到斜率大的，但是这里是分段函数了?
前缀变化会影响父亲的前缀和子段，子段变化则只会影响父亲的子段。于是考虑设计这样的势函数 :
对于一个点的某一个信息，我们定义它的势能是这几个取\(\max\)的东西里面，比当前最优的一项斜率要大的东西的数量，乘上这个点的深度的平方(对于最大前/后缀和)或者深度(对于最大子段和)。总势能是所有点所有信息势能的和。
一开始前/后缀的势能的和是\(O(n\log^2 n)\)，子段是\(O(n\log n)\)。每次修改之后，前/后缀势能的和会增加\(O(\log^3 n)\)，而子段增加\(O(\log^2 n)\)，于是总复杂度是\(O(n\log^3 n+m\log^4 n+q\log n)\)。副标题指的就是这个离奇复杂度（
然后注意到前缀的决策点是递增的，后缀反过来，所以复杂度少了一个\(\log\)，变成了\(O((n+m)\log^3 n+q\log n)\)。实际上表现也很良好。
SNOI2020 区间和
区间取\(\max\)，区间最大子段和。
沿用TB6做法即可（