To improve clarity, we consider the DP from the end.

Imagine starting a piece at coordinate \((i,j)\) and moving it in this way: \(j\mathrel{-}=1\) if \(A_i<B_j\) and \(j\mathrel{-}=1\) if \(A_i>B_j\).

Let’s consider this setup. Experimenting with it reveals the following property:

• Fix a coordinate \((a,b)\). Let \(R(a,b)\) be the rectangular region consisting of the coordinates \((i,j)\) where \(a \leq i\) and \(b \leq j\). When a piece starting from coordinate \((c,d)\) leaves \(R(a,b)\), is the movement horizontal or vertical? The answer is horizontal if \(\min{A[a,c]}<\min{B[b,d]}\) and vertical otherwise.

This property can be proven by induction.

Using this property, we solve the original problem. Since the problem is symmetrical for vertical and horizontal movements, we will only calculate the contribution from \(X\).

When fixing \((a,b)\), the contribution to the answer from the movement \((a,b) \to (a,b-1)\) is \(X_a(\sum_{a\leq c,b \leq d} [\min{A[a,c]}<\min{B[b,d]}] - \sum_{a+1\leq c,b \leq d} [\min{A[a+1,c]}<\min{B[b,d]}])\). The two terms inside the parentheses are almost the same, so we only consider the first term.

We consider taking the sum of \(X_a(\sum_{a\leq c,b \leq d} [\min{A[a,c]}<\min{B[b,d]}])\) while also varying \(a,b\). This is equivalent to taking the following sum:

• For each integer tuple \((a,c,b,d)\) such that \(1 \leq a \leq c \leq N\), \(1 \leq b \leq d \leq M\), and \(\min{A[a,c]}<\min{B[b,d]}\), add to the answer with the coefficient of \(X_a\).

It is important that the condition for \([a,c], [b,d]\) is described only by \(\min\). By classifying \([a,c]\) according to the value of \(\min{A[a,c]}\) and calculating the sum of \(X_a\) for each (similarly for \([b,d]\)), the above sum can be computed.

Any method can be used to classify \([a,c]\) according to the value of \(\min{A[a,c]}\). For example, using the Cartesian Tree of the sequence allows it to be done in \(O(N)\) time.

All other operations can also be performed in \(O(N)\), so this problem can be solved in \(O(N)\) time overall.

Sample Solution