満点解法では以下のクエリを処理できるデータ構造を必要としています。

• \(k\) が与えられる。 \(X\leftarrow X+2^k\) と更新する
• \(k\) が与えられる。 \(X\leftarrow X-2^k\) と更新する
• 現在の \(X\) の最下位bitを求める

解説では std::set を用いて \(X\) の立っているbitのrunを管理することでそれぞれ \(O(\log q)\) 時間で処理していました。

しかし例えばpythonなど標準データ構造に平衡二分木が含まれていないような言語では同じ方針で通すのは定数倍の観点から厳しいです。本解説ではそのような問題に対処するために、上記のクエリを優先度付きキューのみで処理する方法を解説します。

まず以下のクエリを処理できるデータ構造を考えます。

• \(k\) が与えられる。 \(X\leftarrow X+2^k\) と更新する
• 現在の \(X\) の最下位bitを求める

これはまず優先度付きキュー \(S\) を用意し、 \(1\) 番目のクエリでは \(S\) に \(k\) を追加します。 このため、 \(X=\sum_{k \in S} 2^k \) が成り立ちます。 \(2\) 番目のクエリの際、まず \(S\) の最小値を \(m\) とします。 \(S\) に \(m\) が \(2\) つ以上含まれていない場合、最下位bitは \(2^m\) とわかります。そうでない場合、 \(S\) から \(m\) を \(2\) つ削除して（最小値のpop）、 \(S\) に \(m+1\) を追加します。この操作によって \(X=\sum_{k \in S} 2^k \) が保たれたまま、 \(S\) のサイズが減少しているため、いつかは求まります。この操作にかかる時間計算量は \(1\) 番目の追加クエリにかかる計算量で償却できます。 以上より \(O(\log q)\) 時間でクエリを処理できました。

これを用いて最初に述べた \(3\) 種類のクエリを処理します。まず上記のデータ構造を \(addS, subS\) の \(2\) つ用意します。 \(1\) 種類目のクエリでは \(addS\) に、 \(2\) 種類目のクエリでは \(subS\) に \(k\) を追加します。 このようにすると \(X = \sum_{a \in addS} 2^a - \sum_{s \in subS} 2^s\) が成り立ち続けます。 最後に \(3\) 番目のクエリについてですが、まず \(addS, subS\) の最小値を比較します。これらが異なる場合は最下位bitが求まっています。そうでない場合は、最小値を両方から削除します。この操作の後も \(X = \sum_{a \in addS} 2^a - \sum_{s \in subS} 2^s\) は成り立っており、集合のサイズが小さくなっているため、いつかは最下位bitが求まります。この削除操作は追加操作の時間計算量で償却できます。