https://atcoder.jp/contests/abc250/tasks/abc250_e

コンテスト中は解けそうで解けなかったが、シンプルな方法で解けることにあとから気づいて悔やまれた。

Si={a1,…,ai},Ti={bi,…,bi}S_i= \{a_1, \ldots, a_i\}, T_i=\{b_i, \ldots, b_i \} とおくと、S1⊆S2⊆⋯⊆Sn,T1⊆T2⊆⋯⊆Tn S_1 \subseteq S_2 \subseteq \cdots \subseteq S_n, T_1 \subseteq T_2 \subseteq \cdots \subseteq T_n となる。

fi=max⁡{j∣Tj⊆Si},gi=max⁡{j∣Sj⊆Ti}f_i= \max \{j \mid T_j \subseteq S_i \}, g_i= \max \{j \mid S_j \subseteq T_i \} を計算する。例えば fif_i まで計算した後に fi+1f_{i+1} を計算するときは、bfi+1,bfi+2,…,bjb_{f_i+1}, b_{f_i+2}, \ldots , b_j が Si+1S_{i+1} に含まれているかをチェックしていき含まれなくなったら fi+1=j−1f_{i+1}=j-1 とすれば良い。

後は Si=Tj⇔Si⊆Tj,Tj⊆Si⇔i≤gj,j≤fiS_i = T_j \Leftrightarrow S_i \subseteq T_j, T_j \subseteq S_i \Leftrightarrow i \le g_j, j \le f_i でクエリを判定すれば良い。

(Julia, 564 ms) https://atcoder.jp/contests/abc250/submissions/31571164