問題一覧 > 通常問題

No.2195 AND Set

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 136
作問者 : ShirotsumeShirotsume / テスター : 👑 p-adicp-adic
1 ProblemId : 8886 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-01-17 00:28:44

問題文

空集合 $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もしくは右上の雲マークをクリックしてアカウントを作成してください。