Cặp XOR Lớn Nhất · canuc80k2013 · Thuật toán Canuc80k

Cho một dãy số nguyên không âm, tìm giá trị lớn nhất của $a_{i}$ XOR $a_{j}$ trên mọi cặp chỉ số thỏa $i \leq j$ .

Phép XOR được hiểu theo biểu diễn nhị phân $31$ bit của các số không âm. Hai chỉ số không bắt buộc khác nhau: có thể chọn cùng một phần tử, nhưng điều này chỉ tạo giá trị $0$ .

Input

Dòng đầu chứa số nguyên $n$ .
Dòng thứ hai chứa $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ .

Output

In một số nguyên duy nhất là giá trị lớn nhất của $a_{i}$ XOR $a_{j}$ với $1 \leq i \leq j \leq n$ .

Constraints

$1 \leq n \leq 2 \cdot 1 0^{5}$ .
$0 \leq a_{i} \leq 2.147483647 \cdot 1 0^{9}$ .
Phép XOR được xét trên các bit từ $30$ xuống $0$ ; kết quả cũng nằm trong đoạn từ $0$ đến $2.147483647 \cdot 1 0^{9}$ .
Được phép chọn $i = j$ ; riêng khi $n = 1$ , cặp duy nhất cho kết quả $0$ .

Scoring

Subtask $1$ ( $50%$ số điểm): $n \leq 2000$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

5
7 2 12 25 10

Output

Giải thích: Chọn $7$ và $25$ : $7 XOR 25 = 30$ . Không cặp nào trong dãy tạo giá trị lớn hơn $30$ .

Ý tưởng: Chèn mọi số vào Binary Trie 31 mức. Với mỗi số, đi từ bit 30 xuống 0 và chọn nhánh có bit đối nghịch nếu tồn tại để tối đa hóa bit hiện tại của XOR; lấy lớn nhất qua mọi truy vấn.
Tính đúng đắn: Khi truy vấn một số x từ bit cao xuống thấp, nếu nhánh đối nghịch tồn tại thì chọn nó làm bit XOR hiện tại bằng 1; mọi lựa chọn ở bit thấp không thể bù được việc mất bit cao này. Nếu nhánh ấy không tồn tại thì nhánh cùng bit là bắt buộc. Vì Trie chứa mọi số và mọi x đều được truy vấn, giá trị lớn nhất thu được bằng tối ưu trên mọi cặp, kể cả x ghép với chính nó.
Độ phức tạp: Xây Trie và truy vấn mọi số tốn O(31n), bộ nhớ O(31n).
Đối chứng nhỏ: Trên dữ liệu nhỏ, duyệt trực tiếp mọi cặp i ≤ j và lấy giá trị XOR lớn nhất. Đây là mô hình độc lập được dùng cho mười test nhỏ.