Let \(\displaystyle z_i = \sum_{k = 1}^i y_k\), where \(z_0 = 0\).

For \(z_{i - 1} \lt k \leq z_i\), it always holds that \(C_k = x_i\). We will use this property to find the maximum value of \(A_{z_{i - 1} + 1}, \dots, A_{z_{i}}\).
For convenience, let \(A_0 = B_0 = 0\). Then, for \(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} \]

therefore, we can express as \(A_{z_{i - 1} + n} = an^2 + bn + c\). If we denote the left hand side by \(f(n)\), the problem is boiled down to the problem of finding the maximum value of \(f(1), \dots, f(z_i - z_{i - 1})\).

[1] If \(a \geq 0\)

Since \(f(n + 1) - f(n) = 2an + a + b\) is monotonically increasing on \(n\), there exists an integer \(1 \leq m \leq z_i - z_{i - 1}\) such that

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

Therefore, either \(f(1), f(z_i - z_{i - 1})\) is the maximum value.

[2] If \(a \lt 0\)

Since \(f(n + 1) - f(n) = 2an + a + b\) is monotonically decreasing on \(n\), there exists an integer \(1 \leq m \leq z_i - z_{i - 1}\) such that

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

\(f(m)\) is the maximum value.

We describe how to find \(m\) fast using ternary search. Let \(g(n) = f(n + 1) - f(n)\), then \(f(m_2) - f(m_1) = g(m_1) + \dots + g(m_2 - 1)\), so

• if \(f(m_1) \leq f(m_2)\), then \(g(m_1) + \dots + g(m_2 - 1) \geq 0\), and as \(g(n)\) is monotonically decreasing, we have \(g(m_1) \geq 0\). Therefore, \(f(m_1) \leq f(m_1 + 1)\), hence \(m_1 \lt m\).
• if \(f(m_1) \gt f(m_2)\), then \(g(m_1) + \dots + g(m_2 - 1) \lt 0\), and as \(g(n)\) is monotonically decreasing, we have \(g(m_2 - 1) \lt 0\). Therefore, \(f(m_2 - 1) \gt f(m_2)\), hence \(m \lt m_2\).

In either case, \(l < m < r\) is preserved.
By choosing \(\displaystyle m_1 = \left\lfloor \frac{l + r}{2} \right\rfloor, m_2 = \left\lfloor \frac{l + r}{2} \right\rfloor + 1\), the value \(r - l\) is halved in each step, so \(m\) can be found in a total complexity of \(O(\log(z_{i} - z_{i - 1}))\).

Therefore, by finding the maximum value of \(A_{z_{i - 1} + 1}, \dots, A_{z_{i}}\) in the order of \(i = 1, \dots, N\), the problem has been solved in a total of \(O(N \log M)\) time. Here, the values of \(A_{z_{i - 1}}\) and \(B_{z_{i - 1}}\) are required, which can be computed from the equations\(A_{z_{i - 1} + n}\) and \(B_{z_{i - 1} + n}\) in a constant time.

Sample code (C++)

Postscript

For functions \(f : \mathbb{Z} \mapsto \mathbb{R}\) and \(g(n) = f(n + 1) - f(n)\), if \(g(n)\) is monotonically increasing, then \(f(n)\) is said to be concave; if \(g(n9\) is monotonically decreasing, then \(f(n)\) is said to be convex. In order to find the extremum of concave/convex function, techniques like ternary search and golden-selection search are frequently used.