Hints → https://atcoder.jp/contests/arc190/editorial/11918

Let \(S = \{1,2,\ldots,N\}\) and \(I_i = \{L_i,\ldots,R_i\}\).

[1] When it is possible to achieve the goal at cost \(2\) or less

First, the following are clear:

• It is impossible to achieve the goal at cost \(0\).
• Achieving the goal at cost \(1\) is possible only if there exists an \(i\) such that \(I_i = S\).

Next, consider the case of achieving the goal at cost \(2\). Categorizing by the types of operations used, there are three possibilities to consider:

• There exist \(i, j\) such that \(I_i \cup I_j = S\).
• There exist \(i, j\) such that \(I_i \cup (S \setminus I_j) = S\).
• There exist \(i, j\) such that \((S \setminus I_i) \cup (S \setminus I_j) = S\).

For the first case, you only need to check for \(i, j\) such that \(1 \in I_i\) and \(N \in I_j\). This can be verified by greedily choosing the longest \(I_i\) and \(I_j\).

For the second case, the condition is equivalent to \(I_i \subset I_j\). You need to check the existence of pairs of intervals with an inclusion relationship, which can be done by sorting intervals by \(L_i\) or \(R_i\).

For the third case, the condition is equivalent to \(I_i \cap I_j = \emptyset\). You only need to check the case where \(I_i\) is to the left of \(I_j\), i.e. \(R_i < L_j\). Thus, examining \(\min(R)\) and \(\max(L)\) suffices.

With these checks, one can determine whether the goal can be achieved at cost \(2\) or less.

[2] When it is impossible to achieve the goal at cost 2 or less

In this situation in particular, no two intervals have an inclusion relationship. For such intervals, we can appropriately rename the indices so that \(L_1 < L_2 < \cdots\) and \(R_1 < R_2 < \cdots\). Furthermore, since any two intervals must intersect, we get

\(L_1<L_2<\cdots<L_M\leq R_1<R_2<\cdots <R_M\)

From this, we see the following: If \(M \ge 3\), it is possible to achieve the goal at cost \(3\) or less.

Indeed, after re-indexing the intervals as above, it suffices to perform Operation \(1\) on \(I_1\) and \(I_3\), and Operation \(2\) on \(I_2\).

Sample Solution: https://atcoder.jp/contests/arc190/submissions/61252862