GCD Queue

この問題は、Segment Tree というデータ構造を用いて解くことができます。

具体的には以下のようにクエリを処理するとよいです。

まず、変数 $l = 1, r = 1$ を用意します。

そして、

• $1$ のクエリ : Segment Tree の $r$ 番目の値を $x$ に置き換え、$r$ を $1$ 増加させる。
• $2$ のクエリ : Segment Tree の区間 $[l, r)$ の最大公約数を出力し、$l$ を $1$ 増加させる。

あらかじめ Segment Tree の要素数を十分に確保しなければならないことに注意してください。

よって、この問題を $O(Q \log Q)$ で解くことができました。

また、SWAG (Sliding Window Aggregation) を用いて解くこともできます。(当初はこの解法が想定でした。)