问题

给定长度为 n 数组a,b,c，求最大非空子序列使得${\sum }_{i=1}^k{c}_{p_i}+{\sum }_{i=2}^k{a}_{p_i}\cdot b_{p_{i-1}}\backslash sum\_\{i=1\}^\{k\}c\_\{p\_i\}+\backslash sum\_\{i=2\}^\{k\}\; a\_\{p\_\{i\}\}\backslash cdot\; b\_\{p\_\{i-1\}\}$最大（p表示子序列）

思考

用dp[i]表示已经考虑了石子1\dots i，并且选择了石子i的最大开心值，有转移方程

可以发现可以用斜率优化

题解 1

CDQ分治+斜率优化

分治时每次先处理完左半支，然后用左半支已知的dp值造凸包，更新右半支的dp值。

复杂度$O(nlo{g}^{2}n)O(n\; log^2n)$

需要注意的是建造凸包的过程中乘法可能会爆longlong，需要使用int128改成除法double高精度解决。

题解 2

标记永久化线段树，离散化a[i]，之后不断在线段树上加边+查询。

复杂度$O(nlogn)O(n\; log\; n)$

吐槽

Andrea——怎么没把这题A了——