No.2195 AND Set
タグ : / 解いたユーザー数 139
作問者 : Shirotsume / テスター : 👑 p-adic
問題文
空集合 $S$ があります。以下に説明する $Q$ 個のクエリを処理してください。$i$ 番目のクエリは以下の $3$ つの種類のうちいずれか $1$ つです。
- クエリ1 : 集合 $S$ に整数 $x_i$ を追加する。すでに $S$ に $x_i$ が含まれているならば、なにもしない。
- クエリ2 : 集合 $S$ から整数 $x_i$ を削除する。 $S$ に $x_i$ が含まれていないならば、なにもしない。
- クエリ3 : 集合 $S$ に含まれるすべての要素の Bitwise AND を出力する。ただし、 $S$ が空のときは $-1$ を出力する。
Bitwise AND とは(クリックで展開)
$2$ つの非負整数 $X, Y$ について、 $X$ と $Y$ の Bitwise AND、 $X$ $\mathrm{AND}$ $Y$ は以下のように定義されます。
- $X$ $\mathrm{AND}$ $Y$ を $2$ 進表記したときの $2^k$ $(k \geq 0)$ の位は、$X$ の $2$ 進表記での $2^k$ の位と、 $Y$ の $2$ 進表記での $2^k$ の位の両方が $1$ である場合 $1$ 、そうでない場合 $0$
例えば、 $3$ $\mathrm{AND}$ $5 = 1$ です。( $2$ 進表記すると $011$ $\mathrm{AND}$ $101 = 001$)
一般に $k$ 個の非負整数 $p_1, p_2, \dots, p_k$ の Bitwise AND は $( \dots ((p_1$ $\mathrm{AND}$ $p_2)$ $\mathrm{AND}$ $p_3)$ $\mathrm{AND}$ $\dots)$ $\mathrm{AND}$ $p_k)$ と定義され、これは $p_1, p_2, \dots, p_k$ の順番によらないことが証明できます。
制約
- 入力は全て整数
- $1 \leq Q \leq 4 \times 10^5$
- $0 \leq x_i < 2^{30}$
- クエリは問題文にある形式で与えられる。
- クエリ3が少なくとも $1$ 回与えられる。
入力
入力は標準入力から以下の形式で与えられる。
$Q$ $query_1$ $query_2$ $\vdots$ $query_Q$ただし、各クエリ $query_i$ は、以下の形式のいずれかで与えられる。
クエリ1:
$1$ $x_i$
クエリ2:
$2$ $x_i$
クエリ3:
$3$
出力
クエリ3 が与えられた回数を $X$ として、 $X$ 行出力せよ。 $i$ 行目には、 $i$ 回目に与えられたクエリ3に対する答えを出力せよ。
サンプル
サンプル1
入力
7 1 1 1 4 3 2 3 1 1 2 1 3
出力
0 4
$1$ つめのクエリ $3$ が与えられた時点で、 $S = (1, 4)$ です。よって、 Bitwise AND は $0$ です。
$2$ つめのクエリ $3$ が与えられた時点で、 $S = (4)$ です。よって、 Bitwise AND は $4$ です。
複数回同じ値の追加クエリが来たとしても、複数個の値を追加するわけではないことに注意してください。
サンプル2
入力
20 3 1 1 2 0 1 3 1 2 1 1 3 2 0 2 1 2 1 2 1 2 3 2 2 3 1 2 1 2 1 3 2 3 2 1 3
出力
-1 0 -1 2
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。