P3648
李超树用多了已经不会单调队列维护斜率优化了...
首先切的顺序不影响答案。\((x + y)z + xy = x(y + z) + yz\)。更多份同理。
\(sum\) 表示前缀和，\(suf\) 表示后缀和。设 \(f_{i, j}\) 表示前 \(i\) 个数切成 \(j\) 份的最大值。
\(f_{i, j} \gets \max_{k = 1}^{i - 1} (f_{k, j - 1} + suf_{i + 1}(sum_i - sum_k))\).
先拆柿子 \(f_{i, j} - suf_{i + 1}sum_i = f_{k, j - 1} - suf_{i + 1}sum_k\).
看上去很斜率优化，考虑每一层维护一个李超树，李超树带 \(\log\) 过不去。注意到 \(sum\) 和 \(suf\) 都单调考虑单调队列。
对于两个决策点 \(k, j, k < j\)，\(j\) 比 \(k\) 更优满足 \(f_k - suf_{i + 1}sum_k < f_j - suf_{i + 1}sum_j\)。
移项解得 \(\dfrac{f_j - f_k}{sum_j - sum_k} > suf_{i + 1}\)。\(suf\) 单调递减，把 \((sum_i, f_i)\) 看成点，维护一个斜率单调减的单调队列（凸包）。
由于 \(a_i\) 可能为 \(0\)，当 \(sum_j = sum_k\) 时返回极大值。
P6302/P5468
以边为状态 dp。
先将边按 \(p\) 排序，设 \(f_i\) 表示到第 \(i\) 条边，等待烦躁值的最小值。
那么枚举可以转移的边
\(f_i \gets \min_j(f_j + A(p_i - q_j) ^ 2 + B(p_i - q_j) + C)\).
拆：\(f_i - Ap_i^2 - Bp_i^2 - C = -2Ap_iq_j + f_j + Aq_j^2 - Bq_j\).
然后 \(k < j\)，\(j\) 由于 \(k\) 即 \(-2Aq_kp_i + f_k + Aq_k^2 - Bq_k > -2Aq_jp_i + f_j + Aq_j^2 - Bq_j\)，也就是 \(\dfrac{(f_j + Aq_j^2 - Bq_j) - (f_k + Aq_k^2 - Bq_k)}{q_j - q_k} < 2Ap_i\)。
然后可以对每个点开一个单调队列，转移边时从 \(x\) 转移，存到 \(y\) 的单调队列。
转移要求 \(q_j \le p_i\)，可以先把已转移好的边放到按 \(q\) 排列的小根堆里，在处理 \(i\) 之前把 \(q_j < p_i\) 的边压入单调队列。
P11191
差点场切 /kk
由于选的是一段连续区间，考虑找出序列中 \(a_i\) 可以走的最大的左端点，记为 \(could_i\)，这样的话如果询问区间包含 \([could_i, i]\) 就可以走一个。
但是 \(a_i\) 可能相同，维护 \(a_i\) 上一次出现的位置记为 \(lst_{a_i}\)，如果 \([could_{lst_{a_i}}, lst_{a_i}]\) 和 \([could_i, i]\) 同时被包含，就会重复计算贡献，减去即可，相当于 \([could_{lst_{a_i}}, i]\) 区间会造成 \(-1\) 的贡献。
区间内子区间贡献是经典离线二维数点，不多赘述。
现在讲一下如何找到 \(could_i\)，我们可以遍历序列时维护 \(went_{x}\) 表示 \(x\) 这个点能走的最大左端点，如果 \(x\) 指向 \(1\)，那么 \(went_x\) 就是 \(x\) 在序列中最后出现的位置，不然 \(went_x\) 就是 \(x\) 指向点的 \(went\) 的最大值。
此时我们意识到如果出题人放个菊花就能把这个过程卡成 \(O(n^2)\)，考虑使用根号分治优化。
如果一个点的出边数小于等于根号，那么每次暴力找即可。不然每个点开一个 vector 记录它出度大于根号的前驱，在更新完每个点的 \(went\) 后直接对其出度大于根号的前驱进行更新。
然后这时注意 \(went_x\) 由于在 \(x\) 出现前被更新了，所以在 \(x\) 被遍历到之前 \(went_x\) 不能去更新别的点，那么出度小于根号的点暴力找的时候就去找上一次的状态来更新，即 \(could_{lst_y}\)。
标签：suf,13,could,24.10,根号,went,sum,单调 From： https://www.cnblogs.com/KinNa-Sky/p/18462996