Để giải quyết bài toán trên ta cần biết một số kiến thức sau:
1. Max Xor của 1 đoạn từ [1..i] sử dụng Trie
2. Chia block với mỗi block có S phần tử
Ở đây ta đánh số các block từ $0$ đến $m$ để thuận tiện cho việc xử lý với $m$ là số block, khi đó ta gọi:
- $fbl_{i, j}$ là max xor của 1 đoạn con liên tiếp $[l, r]$ thuộc block từ $i$ đến block $j$.
- $fsuf_{i, j}$ là max xor của đoạn con liên tiếp $[l, r]$ mà $i \le l \le r$ và $l, r$ thuộc trong đoạn block từ $j$ đến $m$.
- $fpre_{i, j}$ là max xor của đoạn con liên tiếp $[l, r]$ mà $l \le r \le i$ và $l, r$ thuộc trong đoạn block từ $0$ đến $j$.
Dễ nhận thấy rằng truy vấn $l, r$ của ta sẽ đưa về 2 trường hợp:
- $l, r$ thuộc cùng một block:
- Khi đó, vì $l, r$ thuộc cùng một block nên ta biết rằng $r-l+1 \le S$, và ta có thể duyệt từ $l$ đến $r$ để tìm kết quả.
- $l, r$ không thuộc cùng một block:
- Ta có thể lấy kết quả của $3$ mảng đã tính trước ở trên với:
- $fbl_{bl, br}$ với $bl$ là block chứa $l$ và $br$ là block chứa $r$.
- $fsuf_{l, br-1}$ với $br$ là block chứa $r$.
- $fpre_{r, bl+1}$ với $bl$ là block chứa $l$.
- Với kết quả trên ta còn tính thiếu max xor trong đoạn $[x, y]$ mà $x \in bl$ và $y \in br$ và $l \le x, y \le r$, ta có thể tính kết quả này dễ dàng.
Việc còn lại là chọn giá trị S phù hợp. Để ý rằng độ phức tạp để tiền xử lý 3 mảng trên là $O(log_{max(a)} * (n / S) ^ 2 * S)$ và độ phức tạp của truy vấn là $O(q * log_{max(a)} * S)$. Để thời gian tốt nhất ta chọn S sao cho cực đại của phép tiền xử lý và truy vấn là nhỏ nhất.
Shiba_Engine
Created at
0 likes