概要
問題文 → ■
競技プログラミングでは，長さ $N$ の配列に対して何かをする場合に，適当な条件を満たすインデックス全体などを管理する目的で使うことが多いと思います．利用できる場面はかなり多く，想定解よりも少し悪い計算量での AC に利用できることも多いので，高速な実装を持っておく利点は大きいと思います．
解法
解法1 std::set の利用
言語によっては適切な標準ライブラリの類を利用してそのまま解くことができます．
- 解答例（1781ms）
std::set を利用すると，各時点での集合の要素数を $n$ とするとき本問題の操作がすべてクエリあたり $\Theta(\log n)$ 時間でできます．
以下で取り上げる解法と比べて実行速度はかなり遅いです．これは標準ライブラリの実装に問題があるというよりも，本問の制約のうち値が $N$ 未満の非負整数であるという性質を全く使っていないことに原因がありそうです．
解法2 Fenwick Tree / Segment Tree
Fenwick Tree, Segment Tree などのデータ構造は，列を扱うデータ構造として導入されることが多いと思いますが，集合が要素 $x$ を持つことと配列の $x$ 番目の要素が $1$ であることと対応させるとことで，値の範囲が $[0, N)$ 内の非負整数であるような集合を扱うこともできます．
したがって本問題は，これらのデータ構造を使うと，クエリあたり $\Theta(\log N)$ 時間で解くことができます（事前計算で $\Theta(N)$ 時間での構築が必要です）．
2024/02/11 現在の Library Checker の問題では，Segment Tree 上での二分探索等が利用できる問題は少ないので，これらを verify する問題としても適切かもしれません．
これらのデータ構造を，01 列に特化して高速化することも考えられます．
長さ $N$ の 01 列を，$N/64$ ブロックの長さ $64$ の連続部分列に分割します．長さ $64$ の 01 列は 64bit 符号なし整数として扱えます．また，各ブロックごとに，ブロック内部の総和を考え，それらを列を扱うデータ構造にのせます．結局クエリは，長さ $N/64$ の列と $64$ bit 符号なし整数に対する計算によって処理できます．
これは残念ながら $w=64$ 倍高速化にも $\log_2 w$ 倍高速化にもならないのですが，$\log_2 N$ が $\log_2(N/64)=\log_2N-6$ になることである程度の高速化にはなります．
- 解答例（01 列に特化した Fenwick Tree, 149ms）
解法3 64分木
各要素が葉であるような64分木を構築し，各内部ノードについて，それぞれの子ノード方向に集合の要素が存在するか否かを 64bit 符号なし整数として持ちます．
木の高さを $h$ とすると，本問題で要求される操作はすべて $\Theta(h)$ 時間で行えます．クエリ 3,4 ではセグメント木の二分探索と同様，あるノードから木を適当なところまで登り，降りていくという実装が可能です．同じ深さのノードを高々2箇所しか訪れないことからこのような計算量になります．各ノードでは 64bit 符号なし整数について，$i$ 番目の bit よりも左・右の最初の bit を取得するという計算ができればよく，これは適当な gcc builtin 関数で行えます．
木の高さは $\log_{64}N$ で，オーダー表記では $\Theta(\log N)$ ということになりますが，$2$ 分木と比べると $1/6$ 倍であることからかなりの高速化になります．また長さ $N$ の 01 列を扱う場合の空間は， 64bit 符号なし整数が $\sum_{k=1}^{\infty} N/64^k = N/63$ 個程度で，仮に $N=2^{30}$ でも 130MB 程度です．
- 解答例（41ms）
実装例は gifted infants のものが有名で，例えば ここ から到達可能です．私の実装もほとんどこれをもとにしました．メソッド名の違いや，prev(i) が i を含むか否かなどの違いはあるので，見比べる場合には注意してください．
子ノードの情報を 1bit で表すため，部分木内の要素数の取得等は難しいです．したがって直前・直後の要素の検索はしやすいものの，$k$ 番目の要素の取得などはこのままでは難しいです．
2024/05/04 現在の Library Checker 最速（30ms, Hegdahl さん）
も64分木を利用しています．私の実装が 80ms 程度にしかならず Library Checker 最速提出との差が全然埋まらず悩んでいた時期がありましたが，入出力の差がかなり大きかったようです．
解法4 van Emde Boas tree
以下「vEB木」と表記します．日本の競プロ界では謎木という呼称もあるようです．以下のような資料があります．
- HCPC 北海道大学競技プログラミングサークル勉強会資料
- 謎木速いけど微妙にバｇ・・・バグらないだと！？ （catupper さん）
vEB木の各ノードの部分木は $[0,n)$ に値を持つ集合を表し，それを $\sqrt{n}$ 個の子ノードに分割して管理します．そして，各子ノードに要素が含まれるかという情報を持ちます．この「情報」が $[0,\sqrt{n})$ に値を持つ集合として表せることから，$[0,n)$ に値を持つ集合を表すノードが $[0,\sqrt{n})$ に値を持つ集合を表すノード $\sqrt{n}+1$ 個によって表せるというのが概要です．これによって $[0,n)$ に値を持つ集合を高さ $\Theta(\log\log n)$ の木として扱います（詳細な解説は省略します）．
$2^{24}$ 要素の場合，64分木の場合と比べてわずかに木の高さは小さくなりますが，処理はすこし複雑になります．例えば次の実装例では，64分木とおおよそ同程度の速度を達成しています．
- https://judge.yosupo.jp/submission/76516 （48ms, nor さん）
本問の制約では64分木と比べた利点はほとんどないように感じます．64分木の各種操作は $\Theta(\log n)$ 時間，vEB木の各種操作は $\Theta(\log\log n)$ 時間なので，$n$ が十分大きくなるとvEB木のパフォーマンスの方が良くなるかもしれません．（そのような場合には $n$ に比例する空間を用意するのは難しいので，集合の要素数で空間を抑える実装が必要になるでしょう．単純な解決方法のひとつに配列の代わりにハッシュマップを使うというものがあります．）
