First of all

This problem uses a special DP (Dynamic Programming) so-called “insertion DP.” An easier version is found in EDPC-T Permutation. If you could not figure out this problem, we first recommend you to consider that problem first.

Editorial

We solve by Dynamic Programming. Let us define \(\mathrm{dp}[i][j][k][l] = (\) the number of ways to decide first \(i\) elements such that the current similarity is \(j\) and there are \(k\) elements greater than \(A_i\) and \(l\) elements greater than \(B_i\) remaining\()\).

This DP naively has \(\mathrm{O}(N^4)\) states, and each transition costs \(\mathrm{O}(N^2)\) time, so it barely fits in the execution time limit.

Here, consider a receiving DP. Then, the transition onto \(\mathrm{dp}[i][j][k][l]\) can be represented as a sum of a rectangular region of \(\mathrm{dp}[i-1][j]\) and another of \(\mathrm{dp}[i-1][j-1]\).

Using this fact, the transition can be sped up to \(\mathrm{O}(1)\) time using two-dimensional cumulative sums. With this improvement, this problem has been solved in a total of \(\mathrm{O}(N^4)\) time.

We can also solve it with distributing DP. Since the transition is applied onto a rectangular region, it is sufficient to use two-dimensional imos’ method (translator’s note: is it known enough to international readers? It is a trick of processing multiple “add-onto-segment” queries, basically using cumulative sums).

Sample code in C++ (with receiving DP)