DP を逆から見ることで見通しを良くします．

座標 \((i,j)\) から駒をスタートさせ，\(A_i<B_j\) ならば \(j\mathrel{-}=1\)，\(A_i>B_j\) ならば \(i\mathrel{-}=1\)，と移動させていくと考えます．

この設定のもとで考察してみましょう． 色々手でいじってみると，以下の性質が見つかります．

• ある座標 \((a,b)\) を固定する．座標 \((i,j)\) (\(a \leq i\), \(b \leq j\)) からなる長方形領域を \(R(a,b)\) とする．ある座標 \((c,d)\) からスタートした駒が \(R(a,b)\) を出るとき，それは縦横どちらの移動であるか？ 答えは，\(\min{A[a,c]}<\min{B[b,d]}\) ならば横方向，そうでないなら縦方向．

証明は帰納法で行えます．

この性質を使って元問題を解いていきます． 縦と横で問題が対称的なので，以下では \(X\) の寄与だけを計算します．

\((a,b)\) を固定し，\((a,b) \to (a,b-1)\) という移動による答えへの寄与を考えると，\(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]}])\) になります． ()内の\(2\) 項はほぼ同じ形をしているので，第 \(1\) 項だけ考えます．

\(X_a(\sum_{a\leq c,b \leq d} [\min{A[a,c]}<\min{B[b,d]}])\) を更に \(a,b\) も動かして和を取ることを考えます． すると，次のような和をとっていることと同値です．

• \(1 \leq a \leq c \leq N\), \(1 \leq b \leq d \leq M\), \(\min{A[a,c]}<\min{B[b,d]}\) なる整数組 \((a,c,b,d)\) に対し，\(X_a\) の係数をかけて答えに足し込む．

\([a,c], [b,d]\) の条件が \(\min\) だけで記述できていることが重要です． \(\min{A[a,c]}\) の値ごとに \([a,c]\) を分類し，それぞれに対し \(X_a\) の和を求める（\([b,d]\) についても同様）ことで，上記の問題は計算できます．

\(\min{A[a,c]}\) の値ごとに \([a,c]\) を分類する方法はなんでもよいですが，例えば数列の Cartesian Tree を使うと \(O(N)\) で行えます．

その他の操作もすべて \(O(N)\) で行えるので，この問題は全体でも \(O(N)\) 時間で解けます．

解答例