長さ \(n\) の列の Grundy 数 \(g _ n\) は次の\((1)\) で計算できます。

\[ g _ n = \mathrm{mex}\lbrace g _ i \oplus g _ j \mid n - R \leq i + j \leq n - L \rbrace \tag{1}. \]

しかし、定義のまま愚直に計算しようとすると、全ての \(n=1,\ldots,N\) に対して \(g _ n\) を計算すると最悪の場合 \(\Omega(n ^ 3)\) 時間掛かります。

そこで、多重集合 \(S _ n \coloneqq \lbrace g _ i \oplus g _ j \mid n - R \leq i + j \leq n - L \rbrace\) を差分更新することで、各 \(g _ n\) の計算を高速化することを考えます。

多重集合 \(T _ k \coloneqq \lbrace g _ i \oplus g _ j \mid i + j = k \rbrace\) を定義すると \(\displaystyle S _ n = \bigcup _ {k = n - R} ^ {n - L} T _ k\) なので、次が成り立ちます。

\[S _ n = \begin{cases} \emptyset & \text{if \;}n = 0 \\ (S _ {n - 1} \cup T _ {n - L})\setminus T _ {n - R - 1} & \text{if \;} n \gt 0 \end{cases} \tag{2}.\]

\(S _ n\) に含まれる値 \(v\) の個数 \(C _ v\) により \(S _ n\) を管理すると、\((2)\) に従った \(S _ n\) の更新は全体 \(O(N ^ 2)\) 時間で可能です。

\(\min\) を二項演算とした Segment Tree 上に \(C _ v\) を載せて二分探索を行うことで、\(\mathop{\mathrm{mex}} S _ n\) の計算は \(1\) 回あたり \(O(\log N)\) 時間で計算できます。以上で全ての \(g _ 1, \ldots, g _ N\) を全体 \(O(N ^ 2 \log N)\) 時間で計算できました。

追記 (2022/11/20 3:32)

https://atcoder.jp/contests/abc278/editorial/5257 で示されているように、\(g_n\leq n\) が成り立ちます。この事実を用いると、\(\mathrm{mex}\) の計算で \(C_v\) を愚直に走査しても全体 \(O(N^2)\) 時間で全ての \(g_1,\ldots,g_N\) を計算できます。

あとは、Grundy 数が \(0\) でない盤面から Gdundy 数が \(0\) である盤面に遷移するような操作を (高速に) 計算する手続きを与えることで本問題を解くことができます。

盤面は長さ \(l _ 1, \ldots, l _ m\) の連続部分列たちからなるとします。この盤面の Grundy 数 \(G\) は \(\displaystyle G = \bigoplus _ {i = 1} ^ m g _ {l _ i}\) として計算されます。目標は、\(G \neq 0\) の仮定の下で、\(1\) 回の操作で \(G = 0\) なる盤面へと変化させることです。

\(G \neq 0\) ならば、\(G \oplus g _ {l _ i} \lt g _ {l _ i}\) なる \(i\) が存在します (参考: ニム - Wikipedia)。この \(i\) に対して、\((1)\) より \(g _ a \oplus g _ b = G \oplus g _ {l _ i}\) かつ \(l _ i - R \leq a + b \leq l _ i - L\) なる \(a, b\) が存在します。即ち、長さ \(l _ i\) の連続部分列を左から \(a\) 要素、右から \(b\) 要素残すような操作は \(G = 0\) の盤面を作る有効な操作であり、目標が達成されます。

あとは、\(l _ i - R \leq a + b \leq l _ i - L\) なる \(a, b\) を高速に計算すればよいです。各非負整数 \(x\) に対して

\[U _ x = \lbrace (a, b) \mid a + b \leq N \land g _ a \oplus g _ b = x \rbrace,\]

を前計算しておきます。また、\(U _ x\) の要素を和が広義単調増加となるように予め並べ替えておきます。具体的には、\(a+b\) の昇順に組 \((a,b)\) を走査すると \(O(N^2)\) 時間で計算できます。このとき、\((a, b)\in U _ {G \oplus g _ {l _ i}}\) かつ \(l _ i - R \leq a + b \leq l _ i - L\) を満たす組 \((a, b)\) を \(1\) つ求めるのは二分探索により \(O(\log N)\) 時間で可能です。

以上で本問題を \(O(N ^ 2 \log N)\) 時間で解くことができました。

なお、\(g_n\leq n\) を用いて \(g_n\) の計算を高速化した解法を用いれば、計算量は \(O(N^2)\) となります。