\(A\) の各要素の間に、仮想的な仕切りを作ります。 クエリ \(1\) によって \(A\) の要素が \(-1\) でなくなるとき、その要素を挟む \(2\) つの仕切りを線で繋ぎます。 すると、クエリ \(1\) において \(A _ h = -1\) となる最初の \(h\) を発見する操作は「\(A _ {x \bmod N}\) の左隣の仕切りから、線でつながった仕切りをたどってできるだけ右に行った場所を発見する操作」と言い換えることができます。(正確には、左端と右端がつながっていることを考慮する必要があります。)

したがって、この仕切りたちを union find で管理しつつ、各連結成分において右端の仕切りの番号も同時に管理することで、この問題を \(\mathrm{O}(N + Q \alpha (N))\) の時間計算量で解くことができます。

さらに改善することも出来ます。 \(A\) をワードサイズ \(w\) (非常に雑に言えば、\(w = 32\)) の大きさのブロックに区切って考えます。 \(1\) つのブロックにおいて、\(A _ i = -1\) かどうかの情報を整数で管理すると、ブロック内で最初の \(-1\) を発見する操作は bit 演算で \(\mathrm{O}(1)\) の時間計算量で行うことができます。 ブロック内に \(-1\) が無い場合、\(1\) ブロックをまとめて \(1\) つの要素と見て前述の union find を用いたアルゴリズムを適用することで、\(-1\) が存在するブロックを高速に発見できます。 サイズ \(N\) の union find に \(\Omega(N \log(N))\) 回の find 操作をを行うと \(1\) 回辺りの償却計算量が \(\mathrm{O}(1)\) となることが知られているので、全体で時間計算量は \(\mathrm{O}(N + Q + (N / w) \log(N / w)) = \mathrm{O}(N + Q)\) となります。

実装例 https://atcoder.jp/contests/abc228/submissions/27408315