My Chinese Editorial

Similiar to offical editorial, we only count when \(x_i = i\).

Consider how to solve the problem when \(L , R\) are given. Obviously, there must be at least one interval such that \(L_i = R_i\), or the matching can’t be unique. Then when we have matched all such \(i\), we delete them and then it’s the same problem with smaller \(N\). That is, keep finding intervals which contain only one element unmatched and match them until every intervals got matched.

To solve the origin problem, we use DP, but it seems hard to solve the problem by matching the intervals one by one, when we choose to match \(x\) the next, the number of ways to choose \([L_x,R_x]\) is related to the longest continuous subsequence containing only \(x\) and matched ones, which seems hard to put into a DP formulation.

While the initial match seems hard to work on, considering the last match seems promising. If we matched \(x\) the last, then for the previous intervals, none of them can contain \(x\) otherwise they can’t be chosen, and there’s no constrain on \(x\), so the number of ways are easy to calculate.

Of course, we can’t get the right answer this way, because there might be multiple intervals we can chose to be the last one, but we count all of them. A principle of inclusion-exclusion (PIE) applied to the subsets of them will probably works within the right complexity. I came up with this solution after solving the problem, the implementation is left as an exercise for readers.

To avoid counting multiply, we consider to count only on the smallest index. If we chose \(x\), we need to make every \(y < x\) can’t be chosen, that is, for every \(y\), it’s covered by at least one interval except itself. So, we can make \(f_{i,j}\) denotes the number of ways to chose intervals when there’s \(i\) elements and the leftmost \(j\) of them are constrained to be covered by at least one interval excluding themselves. The answer is \(f_{n,0}\), \(f_{0,0}=1\).

To calculate \(f_{i,j}\), we can simply list all the \(x\) and \(L_x\), and \(x > j\) must satisfy. Since \([L_x , x]\) are all covered by \(x\), so the constraints on them, if there were, will all be satisfied. For \([1,L_x)\), they will all have constraints given by \(x\), so whatever \(j\) is, the new left part will be \(f_{x-1,L_x-1}\). For \(R_x\), it can chose any number between \(x\) and \(i\), that is:

\[ f_{i,j} = \sum\limits_{x = j+1}^i \sum\limits_{L_x = 1}^x f_{x-1,L_x-1}f_{i-x,0}(i-x+1) \]

To make it simpler:

\[ f_{i,j} = \sum\limits_{k = j}^{i-1} \sum\limits_{l = 0}^{k-1} f_{k,l}f_{i-k-1,0}(i-k) \]

And if you implement it, it will give the right answer, but the complexity is \(O(n^4)\).

To make it faster, we can easily eliminate the second sum by letting \(g_i = \sum\limits_{j=0}^{j=i-1} f_{i,j}\), that is:

\[ f_{i,j} = \sum\limits_{k = j}^{i-1} g_kf_{i-k-1,0}(i-k) \]

You can observe that it’s similiar to suffix sum, so it can be turn into:

\[ f_{i,j} = f_{i,j+1} + g_jf_{i-j-1,0}(i-j) \\ g_i = \sum\limits_{j=0}^{j=i-1} f_{i,j} \]

Then it works in \(O(n^2)\) complexity.