We consider a clean way to solve the problem when all types are fixed.

For each \(i\) (\(1 \leq i \leq N\)), let \(d_i\) be the maximum number of type L jobs that can be done by day \(i\) (under the premise that all \(N\) jobs are completed in \(N\) days).

Claim: There exists a solution that simultaneously achieves \(d_i\) for all \(i\), and this is naturally optimal.

The proof is given below.

We consider how to find \(d_i\) concretely.

Forgetting the premise that all \(N\) jobs must be completed in \(N\) days, consider only the type L jobs. Consider greedily doing these jobs as early as possible. Let the days on which type L jobs are performed be \(x_1 < x_2 < \cdots < x_k\).

Similarly, forgetting the premise, consider only the type R jobs. Consider greedily doing these jobs as late as possible. Let the days on which type R jobs are not performed be \(y_1 < y_2 < \cdots < y_k\).

An upper bound for \(d_i\) is the value \(\min(\)“the number of \(j\) satisfying \(x_j \leq i\)”\(,\)“the number of \(j\) satisfying \(y_j \leq i\)”\()\). This value equals \(d_i\).

As a concrete construction, among the type L jobs, perform the \(i\)-th one (in order of job number) on day \(\max(x_i,y_i)\) (*1).

We process the type-change queries. Changing one job to L corresponds to adding one element each to \(x\) and \(y\).

For each \(i\) (\(1 \leq i \leq N\)), define \(e_i=\) “the number of \(j\) satisfying \(x_j \leq i\)” \(-\) “the number of \(j\) satisfying \(y_j \leq i\)”. If we can find \(\sum |e_i|\), we can calculate \(\sum d_i\) from it, and from that find the answer to the problem.

Adding an element to \(x\) or \(y\) corresponds to a range \(\pm 1\) update on \(e_i\). There is a square root decomposition approach that handles general range \(\pm 1\) updates and \(\sum |e_i|\) queries, but its time complexity is \(O(N \sqrt{N})\), and is slow for the constraints of this problem.

Thus, we consider the following approach. When adding \(v\) (\(=\pm 1\)) to the interval \([l,r)\), we classify the values of \(e_i\) in \([l,r)\) by their sign. Then, we process intervals with the same sign together. Using binary search on a segment tree, updates can be performed in \(O(\)number of intervals \(\times \log(N))\) time.

For general range additions, the number of intervals is \(O(N^2)\) in total, but for this problem we can prove that it is \(O(N)\) in total (*2). Thus, applying this update method yields an \(O(N \log N)\) time solution.

Code Example (C++)

(*1) Proof of this part

The proof is easier to see by considering a different approach for solving the problem with fixed types. Specifically, consider the following greedy method:

• Determine the job to perform on days \(1, 2, \ldots\) one by one. If a type L job can be performed (there is a remaining type L job available that day, and performing it still allows all remaining jobs to be completed), perform L; otherwise, perform R.

The correctness of this method follows from the fact that whenever an L job is postponed, there always exists a rearrangement that moves that L to an earlier position. One can also verify that the result of this method coincides with the solution constructed via \(\max(x_i,y_i)\). The condition “there is a remaining type L job available that day” corresponds to \(x_i\), and the condition “performing it still allows all remaining jobs to be completed” corresponds to \(y_i\).

(*2) Proof of this part

The problem is easier to see when formulated as a minimum cost flow problem. Consider the operation of changing one job from R to L, then finding and augmenting along a negative cycle. The structure of this negative cycle is simple: considering the sequence indicating whether each day is used for L or R, it has the structure of rotating a subsequence of this sequence. Note that in practice, flows like R \(\to\) R \(\to\) R may also be augmented, but since the LR sequence does not change, these are omitted. (↓ example of a rotation)

RRLLRRLLRR
         ↑ change this to `L`

RRLLRRLLRL
*  * *   * rotate here

LRLRRLLLRR

The number of intervals in the described solution corresponds to the number of elements involved in these rotations. The number of rotations can be estimated by considering the following potential:

• For each type R job, consider the interval \([x,r]\) where \(x\) is the day it is performed and \(r\) is its deadline. Take the union of all such intervals to obtain a set of intervals. Define the potential as the sum of the lengths of these intervals.

Suppose the change from R to L happens for job \([L_i,R_i]\). For intervals that straddle \(L_i\) or \(R_i\), their lengths do not increase or only decrease after the rotation. For intervals completely contained within \([L_i,R_i]\), their length decreases by \(1\) when processed by the rotation.

This shows that the total number of rotation operations is \(O(N)\).