Từ điển XOR lớn nhất

Buổi 67-68 — Mock IOI Data-structures
Points
80
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions

Đề bài

Duy trì một đa tập hợp $S$ các số nguyên không âm, ban đầu $S = {0}$. Bạn cần xử lý $Q$ truy vấn thuộc ba loại:

  • + x: thêm một bản sao của $x$ vào $S$.
  • - x: xóa một bản sao của $x$ khỏi $S$ (đảm bảo $x$ đang có mặt trong $S$).
  • ? x: tìm giá trị lớn nhất của $x \oplus y$ với $y \in S$ (trong đó $\oplus$ là phép XOR theo bit).

Dữ liệu vào

  • Dòng đầu chứa số nguyên $Q$ ($1 \le Q \le 2 \cdot 10^5$).
  • $Q$ dòng tiếp theo, mỗi dòng có dạng + x, - x hoặc ? x ($0 \le x < 2^{30}$).

Kết quả

Với mỗi truy vấn ? x, in ra kết quả lớn nhất tìm được trên một dòng.

Subtasks

  • Subtask 1 (25%): $Q \le 2000$.
  • Subtask 2 (25%): Không có truy vấn - x.
  • Subtask 3 (50%): Không có ràng buộc thêm.

Ví dụ

Input Output
8
+ 3
+ 5
? 6
+ 10
? 2
- 10
? 2
? 0
6
8
7
5
Draft saved