闲话
今日推歌：
On Your Side - Yasuha.
随之任之 - r-906 feat. 初音ミク
接下来是什么？小孩召开法？
凸包
给定一系列平面上的点 \((x_i, y_i)\)。我们选择一个最小的凸多边形，满足其能包含给定的所有点，这个凸多边形就叫做给定点集合的凸包。
可以想象一块木板上钉钉子，然后用橡皮筋绕一圈产生的形态。
很多时候应用凸包是为了求得取值最大的点。具体地，根据题面条件你可以对贡献构造一个形如 \(y = kx + b\) 的式子，你需要找到 \(\max y\)。这时就需要等维护一个 \(y\) 对 \(x\) 的凸包，并在其上二分得到答案。也有可能点集的贡献是一条过点的直线相关的信息，而确定这条直线的斜率需要用到凸包。
可以直接用单调性或李超树维护，也可以应用 MergeSort Tree 一类的结构。
单调性凸包的维护可以采用叉积。如果 \(|\bm x\times \bm y| \ge 0\) 则 \(\bm x\) 在 \(\bm y\) 的左侧。因此维护上凸包时可以采用叉积的取值判定是否该出栈。
具体看例题。
首先这个式子上下都有 \(i,j\) 相关的项，不好直接求，可以二分答案转化为判定。
设当前二分到的答案为 \(\text{mid}\)，我们就需要判定是否存在一组 \(i,j\) 满足 \(\dfrac{y_i + q_j}{x_i + p_j} \ge \text{mid}\)。式子展开就是 \((y_i - \text{mid}\times x_i) + (q_j - \text{mid} \times p_j) \ge 0\)。我们只需要找到一组 \(i, j\) 使得两个括号内分别的值最大即可。
可以树剖转化为序列上问题，下面只讨论 \(x, y\)。
可以发现我们需要的就是最大的 \(y = kx + b\)，其中 \(x\) 是固定的。容易发现 \(\max y\) 肯定出现在直线形成的凸包上，这可以通过对序列建子区间凸包的 MergeSort Tree 解决。在询问时遍历每个被覆盖的区间，二分找到 \(x\) 对应的最大值即可。这部分的复杂度是 \(O(\log^2 n)\)。
算上前面的树剖和二分，总时间复杂度 \(O(n\log^4 n)\)。大概可以通过 DS 序列的结论分析到 \(O(n\log^3 n)\)。
作前缀和后转化为区间加等差数列区间最大值。其实区间加等差数列的右端点到序列最后都得加一个 \(k\times (r - l + 1)\)，但这个维护简便。
这题 \(k\) 有小于 0 的，KTT 的复杂度分析不能用在这里，所以感觉复杂度就是根号的。没法优化吧？当然如果大佬提出 polylog 做法我举双手赞同。
考虑采用分块求解。我们将序列分为 \(B\) 块，在每块内维护一个凸包。下面讨论一块内信息的维护。
记上次重构后第 \(i\) 个元素为 \(a[i]\)，本块内第 \(i\) 个元素加了 \(k i + b\)。这样第 \(i\) 个元素的值即为 \(y[i] = a[i] + b + ki\)。我们可以将 \(a[i]\) 视作斜率构造凸包，最后的最大值就是斜率为 \(-k\) 的直线所切在的凸包上的位置。具体为什么是 \(-k\) 可以画图观察。这样做的好处是 \(k,b\) 对凸包没有影响，可以单纯视作 lazy 标记维护。
查询整块内的最大值可以在块内元素组成的凸包上二分，散块可以直接下推信息后扫描。复杂度为 \(O(B \log n)\)。
区间加等差数列可以将端点所在的块下推信息后扫描，剩余部分直接加入标记即可。复杂度为 \(O(\dfrac{n}{B})\)。
平衡复杂度得到 \(B = \sqrt{\dfrac{n}{\log n}}\) 最优。当然块长这种东西挺玄学的。
容易发现答案是求最小的 \(\max_i \left\{\text{atk}_i + \text{dnf}_i + \dfrac{a\text{atk}_i}{b} + \dfrac{a\text{dnf}_i}{b}\right\}\)。写出更好看的形式，就是找到 \(k\)，最小化 \(\max_i \left\{ x_i - y_i / k + y_i - kx_i \right\}\)。
容易发现 \(x_i - y_i / k\) 和 \(y_i - kx_i\) 是直线 \(y = kx + (y_i - kx_i)\) 的纵横截距，设 \(f_i(x) = kx + (y_i - kx_i)\)。发现这条直线过 \((x_i, y_i)\)，斜率为 \(k\)。我们只需要对每条直线作决策，找到其截距加和作为最大值出现时对应的 \(k\) 的区间 \([k_l, k_r]\)，在其中选择截距加和最小的 \(k\) 即可。
容易发现一条直线的截距加和作为最大值出现，当且仅当其他所有直线都在其下方。所以我们只需要求出上凸包，若凸包上点 \(i\) 与左右两点形成的直线斜率为 \(k_1, k_2(k_1 < k_2)\)，则直线全体在凸包外时，即 \(k\in (-\infty, k_1] \cup [k_2, \infty)\) 时满足要求。
根据均值不等式可以发现取到全体最大值的 \(k = -\dfrac{y_i}{x_i}\)。如果这个值在范围内我们取这个值即可。如果不在范围内，由于这是对勾函数，我们只需要取 \(k_1, k_2\) 即可。
总时间复杂度为 \(O(n\log n)\)，复杂度瓶颈在于求凸包。
考虑点积的公式：假设其中一个向量是 \((p, q)\)，则其和 \((x, y)\) 的点积就是 \(px + qy\)。由于 \((x, y)\) 固定，可以先提出一个 \(x\)，得到我们需要最大化 \(\frac{y}{x} q + p\)。这显然需要维护上凸壳，然后找到 \(\frac{y}{x}\) 处最大的向量。
然后可以二进制分组来维护，合并的总时间复杂度 \(O(n \log n)\)。具体实现可以采用线段树的结构，第 \(k\) 个向量插在第 \(k\) 个叶子。只有当一个节点对应的段内所有向量都存在时才构造这个节点的凸包。
查询时直接二分 \(O(\log n)\) 个区间取最大值即可。
总时间复杂度 \(O(n \log^2 n)\)，主要是为了学习实现方法。
corner cases 比如说需要维护上下两个凸壳来考虑符号的情况。
这也启发我们设计一类贡献方程形如 \(f_i = \max_j \left\{ k_j x_i + b_j \right\} + c_i\)，这能在 \(O(n\log^2 n)\) 的复杂度内求前 \(n\) 个值。
容易设计出 dp 方程：设 \(f_i\) 为 \(i\) 的答案，有贡献式
\[f_i = \min_{\text{dep}_i - \text{dep}_j \le l_i} \left\{f_j + (\text{dep}_i - \text{dep}_j) p_i + q_i\right\} \]其中 \(j\) 是 \(i\) 的一个祖先，\(f_1 = 0\)。提出没用的项得到
\[f_i = \min_{\text{dep}_i - \text{dep}_j \le l_i} \left\{- \text{dep}_j\times p_i + f_j \right\}+ \text{dep}_i\times p_i + q_i \]把 \(-\text{dep}_j\) 看作斜率。我们可以直接边 dfs 边采用栈记录序列，用线段树套可撤销李超树维护凸壳计算答案。时空复杂度均为 \(O(n\log^2 n)\)。
其实不需要很大的空间复杂度，不用 dfs，而是用树剖转序列，用线段树套李超树维护凸壳计算答案。空间复杂度减为 \(O(n\log n)\)，因为李超树插入直线的空间复杂度为 \(O(1)\)。但时间复杂度为 \(O(n \log^3 n)\)，采用 DS 序列的结论似乎能分析到 \(O(n \log^2 n)\)。
还有一种方法，采用出栈序。如 panyf 的题解分析的，我们考虑采用出栈序（即欧拉序每个点只记录靠右侧的位置）刻画答案。
这样做的好处是不需要考虑到出现两次的情况，异或式贡献不会出现。它可以替代树剖，而且只需要查询一个区间。这样做直接顺承上面的做法可以得到 \(O(n\log^2 n)\) 的时间复杂度。不知道是不是有更紧的下界。
直接套高级数据结构/高级分析方法就能减小复杂度？不懂。
诈骗题面。\(y,z\) 没用，因为可以直接跳过去，反倒是 \(x\) 轴有问题。可以发现这些发展组成了一棵有根外向树，一条 \(u\to v\) 的边表示 \(v\) 比 \(u\) 多了一个 \((x, c)\) 的元素。
对于一次询问，我们需要确定的就是对于一个节点的 \(\max\left\{ (x_0 - x)^2 + c \right\}\)。
套路地展开，得到 \(\max\left\{ -2 x_0 \times x + x_0^2 + x^2 + c \right\}\)。我们考虑设这个答案是 \(b\)，则有
\[x_0^2 + x^2 + c = 2 x_0 \times x + b \]我们考虑一个点的坐标在 \((x, x_0^2 + x^2 + c)\)，仍然是给定斜率，让纵截距最小。延续上面的思路，我们维护点集的凸包，找到斜率是 \(2x_0\) 的后继的直线对应的左端点即可。但是 250MB 的空间。
因此我们离线插入和询问，按斜率从小到大插入，线段树上每个点采用一个凸包直接用单调性维护，就能做到 \(O(n \log n)\) 的空间复杂度。