In each operation that changes the state, we will record one newly painted black square.

Let’s consider whether it is possible to perform operations so that the sequence of recorded squares is \(p_1, p_2, \cdots, p_k\). This can be determined by looking at the operations in reverse order. First, we start with the state where each operation has been performed once. Then, for each \(i = k, \cdots, 1\) in this order, we perform the following operations:

• Check if square \(p_i\) is painted black. If it is white, report failure.

• Undo all operations \(j\) that include \(L_j \leq p_i \leq R_j\).

Now, we need to find the longest sequence of squares for which the answer to this decision problem is Yes.

By the way, after considering \(p_k\), we no longer need to consider any intervals that cross \(p_k\), so the problem is divided into \([1, p_k-1]\) and \([p_k+1, N]\).

Therefore, we can solve this problem using interval DP. Let \(dp[l][r]\) be the optimal solution when only considering operations that are completely contained within the interval \([l, r]\).

To calculate \(dp[l][r]\), we need to check for the last square \(m\) to be painted black in this interval, where \(l \leq m \leq r\). Of course, the only squares that can be chosen as \(m\) are those that are painted black by operations within \([l, r]\). If we calculate the number \(cnt[l][r]\) of operations contained within the interval \([l, r]\) using a cumulative sum, we can determine whether a square \(m\) is painted black by checking if \(cnt[l][m-1] + cnt[m+1][r] < cnt[l][r]\).

The total computational complexity is \(O(N^3)\).

Sample Solution