Từ điển XOR lớn nhất
Points
80
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề 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,- xhoặ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 |
Community Discussion