Let’s better understand the operation of calculating \(f(A)\).

Let’s consider \(y_0\) and \(y_{M+1}\) for convenience. \(y_0\) is always \(0\), and \(y_{M+1}\) increases by \(1\) with each operation.

The sequence \(y\) is always non-decreasing. Therefore, instead of maintaining \(y\) itself, we consider maintaining its differences. We represent \(y\) as a multiset \(s\) that contains \((y_{i+1}-y_i)\) instances of the integer \(i\).

Considering how \(s\) changes with one operation, it boils down to the following:

• Add two instances of \(A_i\) to \(s\). Then, remove one instance of the smallest value from \(s\).

Let’s reinterpret this as a minimum-cost flow problem.

Prepare vertices \(S, T, V_1, \cdots, V_N\) and consider a graph with the following edges:

• Add an edge \(S \to V_i\) with capacity \(2\) and cost \(A_i\).
• Add an edge \(V_i \to V_{i+1}\) with infinite capacity and cost \(0\).
• Add an edge \(V_i \to T\) with capacity \(1\) and cost \(0\).

If we send a flow of capacity \(N\) from \(S\) to \(T\) in this graph at the minimum cost and denote this cost as \(c\), then \(f(x)=2 \times (\sum A_i)-c\).

Since we cannot recalculate the minimum-cost flow every time \(A_i\) changes, we focus on the difference in the optimal flow.

Suppose we have the optimal flow for some \(A\), and now we change the value of \(A_p\).

The current flow we have may not be optimal. Specifically, if there is a negative cost cycle, we need to push it back. Here, before the change in \(A_p\), there were no negative cost cycles in the graph. Therefore, any cycle that needs to be pushed back must pass through the edge \(S \to V_p\) (in either direction).

Moreover, the cycle to be pushed back will always take one of the following two patterns:

• A cycle that flows as \(S \to V_p \to V_q \to S\) for some \(q\).
• A cycle that flows as \(S \to V_q \to V_p \to S\) for some \(q\).

We don’t have time to naively check which \(q\) to use, so we will speed up this part.

First, let’s consider the first type of cycle. To push in the direction \(V_q \to S\), the current flow on \(S \to V_q\) should be at least \(1\). So, we first maintain the set of \(q\) that satisfies this. The range of values in this set that can be chosen as \(q\) forms an interval. If \(p<q\), it can always be used. Even if \(q<p\), when the flows on \(V_q \to V_{q+1} \to \cdots \to V_p\) are all at least \(1\), we can push them back.

By managing the flows on \(V_i \to V_{i+1}\) with a Segment Tree, we can calculate this interval of \(q\) in \(O(\log N)\) time. Then, we just need to find the \(q\) with the smallest pushback cost within the interval. This can also be done with a Segment Tree. More specifically, if the flow on \(S \to V_q\) is \(0\), we should maintain \(\infty\) as the pushback cost.

The second type of cycle can also be quickly checked by creating a Segment Tree. When we find a negative cost cycle, we actually push it back, and the resulting flow changes can all be processed as Segment Tree queries. Particularly, changes in the flows on \(V_i \to V_{i+1}\) will be a range addition query.

Since the capacity of the edge \(S \to V_p\) is \(2\), the pushback occurs at most twice. Therefore, we can calculate the changes for one query in \(O(\log N)\) time.

In summary, this problem can be solved with a total computational complexity of \(O((N+Q) \log N)\).

Sample Solution