NANDの性質を考えます。bitごとに見て、01列を考えます。

\(A = (\dots , 0,1,\dots,1)\) のように途中で \(0\) が来る場合、そこまでの NAND を取ると必ず \(1\) になります。よって、最後の \(0\) を見て、その後の全ての要素が \(1\) の時を考えます。これは、\(1,0,1,0,\dots\) のように変化するので、最後の \(1\) の長さが偶数なら \(1\) になります。

\(A = (0,1,\dots,1)\) の場合は、\(0,1,0,1,\dots\) のように変化するので、全体の長さが偶数なら、\(1\) になります。

\(A= (1,\dots,1)\) の場合は、\(1,0,1,0,\dots\) のように変化するので、全体の長さが奇数なら、\(1\) になります。

よって、最後の \(0\) の要素の位置を取得すれば解けますが、これは、 \(\max\) を取得するセグメント木で解けます。