dp[k]\mathrm{dp}[k]dp[k] (0≤k≤N−1)(0 \le k \le N-1)(0≤k≤N−1) を、 i=1,2,3,⋯ ,ki=1,2,3, \cdots ,ki=1,2,3,⋯,k まで操作して数列 A,BA,BA,B が kkk 項めまで一致するときの Ak+1A_{k+1}Ak+1 の値としてあり得る整数の集合とします。 dp[k]\mathrm{dp}[k]dp[k] が区間であるとき、 dp[k+1]\mathrm{dp}[k+1]dp[k+1] も必ず区間となります。よって、 dp[k]\mathrm{dp}[k]dp[k] を区間として管理すると O(N)O(N)O(N) 時間で判定できます。