ABC341G 题解

blog。妈的，被 trick 干爆了。

\(\textbf{Trick}\)：将所有 \(N_i=(i,\sum\limits_{j=1}^i a_j)\) 视作一点，则区间 \([l,r]\) 的平均值为 \((N_{l-1},N_r)\) 的斜率。
\(\textbf{Prove}\)：由 \(\text{slope}=\dfrac{y_2-y_1}{x_2-x_1}\) 易证。

根据这个 trick，\(k\) 的答案即为 \(k\le r\le n\) 中 \((N_{k-1},N_r)\) 斜率最大的一个。从后往前维护上凸壳即可。

code，时间复杂度 \(O(n)\)。