XOR đoạn con lớn nhất

Hướng tiếp cận

Đây là một bài toán kinh điển kết hợp XOR tiền tố với trie nhị phân để tìm cặp giá trị có XOR lớn nhất.

Nhận xét quan trọng

Đặt $p_0=0$ và $p_i=a_1\oplus a_2\oplus \cdots \oplus a_i$ với $1\le i\le n$. Vì XOR là phép có nghịch đảo bằng chính nó nên XOR của đoạn $[l,r]$ là

$$a_l\oplus a_{l+1}\oplus \cdots \oplus a_r=p_r\oplus p_{l-1}.$$

Bài toán trở thành: cho tập $\{p_0,p_1,\dots ,p_n\}$, tìm cặp $(i,j)$ với $0\le i<j\le n$ sao cho $p_i\oplus p_j$ là lớn nhất.

Khi cho phép $i\le j$ thì cặp $(j,j)$ luôn cho giá trị $0$, nên kể cả nếu coi $i=j$ là hợp lệ cũng không ảnh hưởng cực đại — miễn là tập có ít nhất hai phần tử (luôn đúng vì $p_0$ luôn có mặt).

Thuật toán

Duyệt theo thứ tự $j=0,1,\dots ,n$ và duy trì một trie nhị phân 30 bit (bit cao $\to$ bit thấp) chứa các giá trị $p_0,p_1,\dots ,p_{j-1}$.

1. Khởi tạo trie rỗng rồi insert $p_0=0$. Đây là bước bắt buộc: nếu thiếu, các đoạn dạng $[1,r]$ sẽ không được xét vì $p_r\oplus p_0=p_r$ không có cách nào sinh ra.
2. Với mỗi $j$ từ $1$ đến $n$:
   • Truy vấn trie để tìm giá trị $x$ trong trie cực đại hoá $x\oplus p_j$: đi từ bit cao xuống bit thấp; tại mỗi bit, ưu tiên rẽ sang nhánh có bit ngược với bit hiện tại của $p_j$ (nếu nhánh đó tồn tại), ngược lại đi theo nhánh còn lại.
   • Cập nhật đáp án: $\text{ans}\leftarrow max(\text{ans},x\oplus p_j)$.
   • Insert $p_j$ vào trie.
3. Khi $n=1$, trie ban đầu chứa $p_0=0$, truy vấn cho $p_1=a_1$ trả về $0\oplus a_1=a_1$ — đúng đáp án.

Cài đặt trie mảng (C++)

Dùng hai mảng nxt[N*30 + 10][2] để biểu diễn cây. Mỗi lần insert/query là $O(30)$. Tổng cộng $O(30n)$ ô nhớ.

Cài đặt Python

Vì Python chậm hơn nhiều lần, ta dùng trie dạng mảng phẳng nxt = [[0,0]] * (n*30 + 5) (cấp phát một lần) và sử dụng các phép dịch bit. Đọc dữ liệu bằng sys.stdin.buffer.read() để tăng tốc.

Độ phức tạp

• Thời gian: $O(30n)$.
• Bộ nhớ: $O(30n)$ cho trie.