\(\displaystyle z_i = \sum_{k = 1}^i y_k\) と定めます。ただし、\(z_0 = 0\) とします。

\(z_{i - 1} \lt k \leq z_i\) のときつねに \(C_k = x_i\) が成り立ちます。このことを用いて、\(A_{z_{i - 1} + 1}, \dots, A_{z_{i}}\) の最大値を求める方法を説明します。
便宜上 \(A_0 = B_0 = 0\) とすると、\(1 \leq n \leq z_i - z_{i - 1}\) に対して

\[ \begin{aligned} B_{z_{i - 1} + n} &= B_{z_{i - 1}} + \sum_{k = 1}^n C_{z_{i - 1} + k} \\ &= B_{z_{i - 1}} + \sum_{k = 1}^n x_i \\ &= B_{z_{i - 1}} + x_i n \end{aligned} \]

\[ \begin{aligned} A_{z_{i - 1} + n} &= A_{z_{i - 1}} + \sum_{k = 1}^n B_{z_{i - 1} + k} \\ &= A_{z_{i - 1}} + \sum_{k = 1}^n (B_{z_{i - 1}} + x_i k) \\ &= A_{z_{i - 1}} + B_{z_{i - 1}}n + x_i \times \frac{n(n + 1)}{2} \end{aligned} \]

が成り立ちます。よって、\(A_{z_{i - 1} + n} = an^2 + bn + c\) の形で表せることがわかります。右辺を \(f(n)\) とおくと、\(f(1), \dots, f(z_i - z_{i - 1})\) の最大値を求める問題に言い換えられます。

---

[1] \(a \geq 0\) のとき

\(f(n + 1) - f(n) = 2an + a + b\) は \(n\) について単調増加であるので、次の条件をともに満たす整数 \(1 \leq m \leq z_i - z_{i - 1}\) が存在します。

• \(f(1) \geq \dots \geq f(m) \)
• \(f(m) \lt \dots \lt f(z_i - z_{i - 1})\)

よって \(f(1), f(z_i - z_{i - 1})\) のいずれかが最大値を与えます。

---

[2] \(a \lt 0\) のとき

\(f(n + 1) - f(n) = 2an + a + b\) は \(n\) について単調減少であるので、次の条件をともに満たす整数 \(1 \leq m \leq z_i - z_{i - 1}\) が存在します。

• \(f(1) \leq \dots \leq f(m) \)
• \(f(m) \gt \dots \gt f(z_i - z_{i - 1})\)

\(f(m)\) が最大値を与えます。

三分探索という手法を用いて \(m\) を高速に求める方法を説明します。
まず、\(l := 0, r := z_i - z_{i - 1} + 1\) と定めます。\(l < m < r\) という条件を保ちながら \(r - l\) の値を小さくしていくと、\(r - l = 2\) となった時点で \(m\) の値が分かります。
\(r - l > 2 \) のとき、\(l < m_1 < m_2 < r\) となる \(m_1, m_2\) をとり、次の操作を行います。

• \(f(m_1) \leq f(m_2)\) ならば \(l\) を \(m_1\) で置き換える。
• \(f(m_1) \gt f(m_2)\) ならば \(r\) を \(m_2\) で置き換える。

このとき、\(l < m < r\) が保たれることを示します。\(g(n) = f(n + 1) - f(n)\) とおくと \(f(m_2) - f(m_1) = g(m_1) + \dots + g(m_2 - 1)\) であるので、

• \(f(m_1) \leq f(m_2)\) のとき \(g(m_1) + \dots + g(m_2 - 1) \geq 0\) であるので、\(g(n)\) が単調減少であることとあわせて \(g(m_1) \geq 0\) を得る。したがって \(f(m_1) \leq f(m_1 + 1)\) より \(m_1 \lt m\) である。
• \(f(m_1) \gt f(m_2)\) のとき \(g(m_1) + \dots + g(m_2 - 1) \lt 0\) であるので、\(g(n)\) が単調減少であることとあわせて \(g(m_2 - 1) \lt 0\) を得る。したがって \(f(m_2 - 1) \gt f(m_2)\) より \(m \lt m_2\) である。

いずれの場合も \(l < m < r\) が保たれることが分かります。
\(m_1, m_2\) として \(\displaystyle m_1 = \left\lfloor \frac{l + r}{2} \right\rfloor, m_2 = \left\lfloor \frac{l + r}{2} \right\rfloor + 1\) を選ぶことで、\(r - l\) の値が \(1\) ステップごとに約半分になるので、\(O(\log(z_{i} - z_{i - 1}))\) の計算量で \(m\) を求めることができます。

---

以上から、\(i = 1, \dots, N\) の順に \(A_{z_{i - 1} + 1}, \dots, A_{z_{i}}\) の最大値を求めていくことにより、この問題を \(O(N \log M)\) で解くことができました。なお、\(A_{z_{i - 1}}, B_{z_{i - 1}}\) の値が必要となりますが、これらは \(A_{z_{i - 1} + n}, B_{z_{i - 1} + n}\) の式から定数時間で計算していくことができます。

実装例 (C++)

補足

関数 \(f : \mathbb{Z} \mapsto \mathbb{R}\) について \(g(n) = f(n + 1) - f(n)\) とおいたとき、\(g(n)\) が単調増加であるならば \(f(n)\) は下に凸であるといい、\(g(n)\) が単調減少であるならば \(f(n)\) は上に凸であるといいます。凸関数の極値を求めるために三分探索や黄金分割探索などの手法が頻繁に用いられます。