---
author: little
tags: LRXOR
title: LRXOR Solution
---

$\Huge\text{LRXOR Solution}$

-------

:::info
🔗 Links: [Đề bài](https://drive.google.com/file/d/14-FTNQwh6k8yXiXnIIew8g6CCPy0FvDm/view?usp=share_link)
📌 Tags: `bitmask` `data structures`
✍️ Writer: little
📋 Content:
[TOC]
:::

-----

## Giới Thiệu Đề Bài

Cho dãy số $a$ gồm $n$ phần tử, tìm dãy con liên tiếp có tổng $xor$ lớn nhất. Tức là tìm đoạn $a[l..r]$ sao cho $a[l]$ ^ $a[l+1]$ ^ $...$ ^ $a[r-1]$ ^ $a[r]$ lớn nhất.

-----

## Thuật toán

Có một nhận xét khá quan trọng để $AC$ bài này, gọi $pre[i]$ là tổng $xor$ của các phần tử từ $1$ đến $i$. Ta có: tổng $xor$ của đoạn $[l, r]$ bằng $pre[r]$ ^ $pre[l - 1]$.

Như vậy bài toán sẽ trở thành: khi ta xét đến phần tử thứ $i$, ta sẽ tìm $1$ phần tử $j$ ở trước đó sao cho $pre[i]$ ^ $pre[j]$ lớn nhất.

Để làm được điều đó, ta sử dụng một cấu trúc dữ liệu gọi là $cây$ $tiền$ $tố$ [trie](https://vnoi.info/wiki/algo/data-structures/trie.md). Mỗi nút của cây $trie$ sẽ lưu một giá trị $0$ hoặc $1$. Khi đi từng nút của cây $trie$ ta sẽ đi sang trái nếu nút đó có giá trị là $0$ và sang phải nếu nó là $1$.

Ban đầu cho $ans$ $=$ $0$, ta sẽ duyệt từng $bit$ một theo thứ tự từ trái sang phải (tức là từ bit lớn nhất về bit nhỏ nhất). Nếu như $bit$ $i$ hiện tại là $0$ thì ta sẽ ưu tiên rẽ qua phải (bởi vì khi rẽ phải thì ta sẽ có bật được $bit$ thứ $i$ lên đồng nghĩa với việc $ans$ của chúng ta sẽ lớn hơn). Còn nếu $bit$ $i$ hiện tại là $1$ thì ta sẽ rẽ trái. Và tất nhiên nếu như chỉ có duy nhất $1$ sự lựa chọn là rẽ trái hoặc rẽ phải thì ta phải đi theo đó.

Với mỗi lần rẽ phải hoặc trái, ta sẽ cập nhật kết quả $ans$ luôn.

Vậy độ phức tạp bài toán sẽ là $O(n * log(max(a[i])))$.

----

Tham khảo code ở [đây](https://ideone.com/H1dwTk)