素因数分解をしない解法です。

オイラーの規準の一般化である次の命題が成り立ちます：

\(n\) を正整数、\(p\) を \(p\equiv1\pmod n\) であるような素数とする。 \(p\) で割り切れない整数 \(a\) に対し
\(a\bmod p\) が \(n\) 乗剰余 \(\iff a^{\frac{p-1}{n}}\equiv1\pmod p\)

\(3\) で割ると \(1\) 余るような十分大きな素数 \(P_1,\dots,P_K\) を独立ランダムに選んでおき、 各 \(j=1,\dots,K\) に対して \({}\bmod P_j\) で問題を解けば良いです。 すなわち、各 \(j\) に対して累積積 \(S_{i,j}=A_1\times\dots\times A_i\bmod P_j\) を計算しておき、 クエリ \(L_i,R_i\) に対して \(S_{R_i,j}S_{L_i-1,j}^{-1}\bmod P_j\) が立方剰余かどうかを上の命題を使って判定します。 全ての \(j\) に対して立方剰余ならYes、そうでなければNoを出力します。

計算量は \(O((N+Q\log\max\limits_jP_j)K)\) です。

この解法により誤判定される確率を評価します。
\(a\) が立方数ならばもちろん全ての \(j\) に対して \(a\bmod P_j\) は立方剰余です。
\(a\) を立方数でない整数とします。 \(1\) 以上 \(P_j\) 未満の整数の中で \({}\bmod P_j\) で立方剰余であるものの割合は \(1/3\) なので、 \(a\bmod P_j\) が立方剰余となる確率はおよそ \(1/3\) です[注]。 すなわち誤判定してしまう確率はおよそ \(1/3^K\) と推測できます。 つまり \(K\) を \(20\) 程度にすれば十分高い確率でACすることができます。

[注]: ランダムに選ばれているのは \(a\) ではなく \(P_j\) の方なのでこの説明は不正確です。実際には、 \(a\) が立方数でないとき「\(3\) で割ると \(1\) 余る素数の全体」における「\(3\) で割ると \(1\) 余り、 \(a\) が立方剰余になるような素数の全体」の「割合」が \(1/3\) であることは代数的整数論により示すことができます。