分割統治法を使います。

区間 \([l,r]\) に完全に含まれる区間のみを考えているとき、\(m= \lfloor\frac{l+r}{2} \rfloor\) として、\([l,m]\) と \([m+1,r]\) については再帰的に処理し、\(m\) と \(m+1\) の両方を含む区間のみを考えれば良いです。

• \(C_i\,(l \leq i \leq m) = \min(A_i,A_{i+1},\ldots,A_{m})\)
• \(D_i\,(l \leq i \leq m) = \min(B_i,B_{i+1},\ldots,B_{m})\)
• \(E_i\,(m+1 \leq i \leq r) = \min(A_{m+1},A_{m+2},\ldots,A_i) \)
• \(F_i\,(m+1 \leq i \leq r) = \min(B_{m+1},B_{m+2},\ldots,B_i) \)

とそれぞれ定義すると、\([i,j](l \le i \le m, m+1 \le j \le r)\) のスコアは \(|\min(C_i,E_j)-\min(D_i,F_j)|\) です。

\(j-i=k\) を満たす \([i,j]\) のスコアの最小値を高速に求めます。

以下の \(4\) 種類の場合分けを行います。

• \(\min(C_i,E_j)=C_i\) かつ \(\min(D_i,F_j)=D_i\)
• \(\min(C_i,E_j)=E_j\) かつ \(\min(D_i,F_j)=F_j\)
• \(\min(C_i,E_j)=C_i\) かつ \(\min(D_i,F_j)=F_j\)
• \(\min(C_i,E_j)=E_j\) かつ \(\min(D_i,F_j)=D_i\)

\(C,D\) はそれぞれ単調に増加し、\(E,F\) はそれぞれ単調に減少するので、上の \(4\) つのそれぞれに当てはまる \(i\) は区間となり、この区間は二分探索によって求められます。

上の \(2\) つの場合は、区間最小値取得のデータ構造を用いて高速に求めることができます。

下の \(2\) つの場合は、単調減少の数列と単調増加の数列との要素の差の最小値を求める問題に帰着されるので、大小が切り替わる点を二分探索で求めればよいです。

よってこの問題が \(O(N \log^2N)\) で解けました。

なお、尺取り法とスライド最小値を用いることで、\(O(N \log N)\) で解くことも可能です。

writer 解 \((O(N \log N))\)：https://atcoder.jp/contests/nadafes2022_day2/submissions/30972100

tester 解 \((O(N \log^2N))\)：https://atcoder.jp/contests/nadafes2022_day2/submissions/31081182