\(A\) の先頭 \(x\)​ 項に含まれる値の集合を \(SA_x\)、 \(B\) の先頭 \(x\)​ 項に含まれる値の集合を \(SB_x\) とします。

\(SA_x,SB_x\) はともに \(x\) の増加により(包含関係による順序で)単調増加することから、各 \(x\) に対して\(SA_x=SB_y\) が成り立つような \(y\) は区間になることがわかります。そのような区間を \(I_x\) とおいたとき、さらに以下が成り立ちます。

• \(SA_x=SA_{x'}\Longrightarrow I_x=I_{x'}\)
• \(SA_x\subsetneq SA_{x'} \Longrightarrow \max I_x < \min I_{x'}\)

したがって、これらを使いつつ、\(SA_x \cap SB_y, SA_x \setminus SB_y, SB_y\setminus SA_x\) の\(3\) つをそれぞれsetで管理することで、尺取法の要領で全ての \(x\) についての \(I_x\) を \(O(N\log N)\) 時間で求めることができます。

実装例(Python)