Vasiliy's Multiset [Codeforces 367 : Div2 D]

問題

http://codeforces.com/contest/706/problem/D

多重集合Aがあり、0が入っている。
これに対して、q個の以下のクエリを処理せよ。

1. "+ x" Aにxを入れる
2. "- x" Aからxを消す
3. "? x" Aから1つ選んだ要素yについて、xとyのXORの最大値を出力

1 <= q <= 2*10^5
1 <= xi <= 10^9

帰納的考察（他人のプログラムを読んだ）

1. qが10^5なので1クエリO(log n)かO(1)で解く必要がある
2. わ　か　ら　ん

――壁――

3. 「XORの最大値はビット毎に決定していけば取れる」という知見を得た
4. xiが10^9ということは、30ビットに収まるので、30ビットを順に決定する
5. クエリの1と2はそのままmultisetを使って扱おう（十分速い）
6. 3の動作を工夫して行う

7. 先頭ビットから確定していくが、lower_boundを使うと、対数時間で確定した先頭ビットから最も距離が近い数を探し出せる
8. 下からではなく先頭から確定させていくのがポイント

実装

http://codeforces.com/contest/706/submission/19973738

// original : http://codeforces.com/contest/706/submission/19817882
#define rrep(i,a,b) for(int i=a;i>=b;i--)
int q;
multiset<int> ms;
//-----------------------------------------------------------------
int main() {
	scanf("%d", &q);
	ms.insert(0);
	rep(qq, 0, q) {
		char c;
		int x;
		scanf(" %c %d", &c, &x);

		if (c == '+')
			ms.insert(x);
		else if (c == '-')
			ms.erase(ms.find(x));
		else {
			int ans = 0;
			rrep(i, 29, 0) {
				ans |= (~x & (1 << i));
				auto ite = ms.lower_bound(ans);
				if (ite == ms.end() || ans + (1 << i) <= *ite) ans ^= 1 << i;
			}
			printf("%d\n", ans ^ x);
		}
	}
}