This problem uses a technique for speeding up flow algorithms with segment trees. (It is sometimes informally called the maroon technique, as maroon has used this type of problem as the hardest problem in a contest on about two occasions.)

First, we can see that the objective is a problem known as the dual of a minimum-cost flow problem. (The editorial for ABC393-G explains this dual in great detail; please refer to it.)

Thus, relaxing the variables to real numbers and taking the LP dual is valid. The answer after taking the dual is \(-1\) times the cost of a minimum-cost circulation in the graph constructed below. (The same editorial also explains how to derive the dual in detail.)

• Construct a graph with \(N+1\) vertices consisting of a supervertex \(S\) and vertices \(1, 2, \dots, N\), and add the following edges:
  • For \(1 \leq i \leq N\), add an edge from \(S\) to vertex \(i\) with capacity \(g_i\) and cost \(-A_i\).
  • For \(1 \leq i \leq N\), add an edge from vertex \(i\) to \(S\) with capacity \(g_i\) and cost \(A_i\).
  • For \(1 \leq i \leq N-1\), add an edge from vertex \(i\) to vertex \(i+1\) with capacity \(d_i\) and cost \(0\).
  • For \(1 \leq i \leq N-1\), add an edge from vertex \(i+1\) to vertex \(i\) with capacity \(d_i\) and cost \(0\).

We need to maintain this minimum cost as \(A_i\) changes.

The intended solution expresses updates to \(A_i\) as \(\mathrm{O}(Q)\) insertions and deletions of edges with capacity \(1\).

Let us first explain why. Changing \(A_i\) changes only the costs of \(S \to i\) and \(i \to S\). Temporarily remove these \(2\) edges, change \(A_i\), then add them back with their new costs. An edge with capacity \(g_i\) can be regarded as \(g_i\) edges with capacity \(1\) and the same cost. Since \(g_i \leq 2\), the number of edges inserted and deleted in \(1\) query is constant.

Let the current graph be \(G\), its minimum-cost circulation be \(f\), and the residual graph be \(G_f\). Recall that \(f\) is optimal if and only if \(G_f\) has no negative-cost cycle. Process the insertion or deletion of an edge \(e\) with capacity \(1\) as follows:

• Inserting \(e\): In \(G_f+e\), find a minimum-cost cycle containing \(e\). If its cost is negative, send \(1\) unit of flow along it. Otherwise, do nothing.
• Deleting \(e\): If the flow of \(e\) is \(0\), simply delete it. If its flow is \(1\), send \(1\) unit of flow along a minimum-cost cycle containing the reverse edge of \(e\), returning the flow of \(e\) to \(0\), then delete it. In this case, we must send flow even if the cycle’s cost is nonnegative.

For detailed explanations with proofs, see the official editorial and maspy’s user editorial for ABC363-G.

Finally, use the structure of this graph to speed up cycle searches and flow updates with segment trees.

The cycles we consider have the form \(S \to i \to \cdots \to j \to S\), traveling along the path between \(i\) and \(j\). All edges on the path have cost \(0\), so the cost of this cycle is \(A_j-A_i\).

First, maintain the residual capacities in the rightward and leftward directions along the path in \(2\) lazy segment trees supporting range addition and range minimum queries.

The vertices reachable from \(i\) along the path form a contiguous interval in each direction, ending at the first edge whose residual capacity in that direction is \(0\). Binary search on the segment tree with the condition “the minimum residual capacity over the interval is positive” finds this range in \(\mathrm{O}(\log N)\) time.

Also, prepare a segment tree for range minimum queries, storing \(A_j\) at vertex \(j\) if the residual edge \(j \to S\) is available, and \(+\infty\) otherwise.

Find the minimum value and its position among vertices in the reachable range satisfying \(j \ne i\). This gives the minimum-cost cycle using the residual edge \(S \to i\).

For a cycle using the residual edge \(i \to S\), find the range of vertices \(j\) from which \(i\) is reachable, and use one more segment tree to find the minimum of \(-A_j\) among vertices where \(S \to j\) is available. Here, the residual-capacity direction examined on each side must be reversed.

Sending \(1\) unit of flow along a cycle changes the residual capacities of the traversed path interval by \(-1\) in the flow direction and \(+1\) in the reverse direction. Handle this with range additions.

The capacities of residual edges incident to \(S\) change only at vertices \(i,j\), so the segment trees maintaining vertex costs need only point updates.

Thus, cycle searches and updates require a constant number of segment tree queries, letting us process each insertion or deletion of an edge with capacity \(1\) in \(\mathrm{O}(\log N)\) time.

Implementing these ideas appropriately solves the problem in \(\mathrm{O}((N + Q) \log N)\) time, which is sufficiently fast.

• Sample implementation, C++

Related problems

Similar problems have appeared in various contests. You can use them for practice.

• ABC363 G: Dynamic Scheduling
• The 5th Universal Cup. Stage 3 D: Dynamic Adjustment
• JOI 2025 / 2026 Final Round: Scarecrow 2
• ARC168 F: Up-Down Queries
• NIKKEI Programming Contest 2019 Final H: Homework Scheduling