Để làm được bài này bạn đọc cần biết về [XOR Hashing](https://codeforces.com/blog/entry/85900) và [Chia căn](https://usaco.guide/plat/sqrt?lang=cpp).
## Phân tích điều kiện xuất hiện lẻ lần
Sử dụng kỹ thuật XOR Hashing để gán cho mỗi giá trị $x$ một hash ngẫu nhiên $h(x)$. Ta nhắc lại một tính chất quen thuộc của phép xor: $a \oplus a = 0$, hay tổng quát hơn:
$$
\underbrace{a\oplus a \oplus \ldots \oplus a}_{\text{số chẵn lần}} = 0
$$
Như vậy khi ta dùng XOR Hashing để băm một multiset mà $x$ xuất hiện chẵn lần thì $h(x)$ sẽ không có đóng góp gì vào giá trị hash sau cùng.
Qua đó ta có nhận xét quan trọng nhất cho bài toán: Một đoạn $a[l\ldots r]$ thỏa mãn khi và chỉ khi hash của đoạn $[l, r]$ bằng hash của các **giá trị phân biệt** trong đoạn.
## Lời giải
Để tính xor các giá trị phân biệt trong một đoạn $[l, r]$ ta cố định $l$ là duyệt từ $n\rightarrow 1$. Mỗi khi "quét đến" $a_l$, ta sẽ gán giá trị gần nhất bên phải bằng $a_l$ (nếu có) thành $0$, khi đó xor của đoạn $[l, r]$ chính là xor các giá trị phân biệt.
Như vậy ta có ý tưởng thực hiện như sau:
- Cố định đầu $l$ và duyệt từ phải qua trái
- Duy trì $pref_r = (h(a_l) \oplus h(a_{l + 1}) \oplus \ldots \oplus h(a_{r})) \oplus (\text{XOR các giá trị phân biệt trong đoạn }[l, r])$
- Khi gặp $a_l$, gọi $\texttt{last}[a_l]$ là vị trí gần nhất bên phải bằng $a_l$ (nếu có).
- Thực hiện xor đoạn $[\texttt{last}[a_l], n]$ cho $h(a_l)$ (việc này sẽ cập nhật lại $pref_r$, để dễ hình dung thì bạn đọc nên vẽ ra và chú ý tính khử nhau của phép xor).
- Như vậy số đoạn thỏa mãn có mút trái $l$ chính là số giá trị $0$ trong đoạn $pref[l\ldots r]$.
Ta cần một cấu trúc dữ liệu hiệu quả để duy trì $pref$, trong lời giải này tác giả sử dụng chia căn, cụ thể là:
- Chia mảng $pref$ thành các block độ dài $\sqrt{n}$, gán cho mỗi block một nhãn $\texttt{lazy}$ là giá trị xor được cập nhật lên block.
- Với mỗi truy vấn xor đoạn $[l, r]$, ta cập nhật $\texttt{lazy}$ của các block nguyên vẹn và thủ công với các block ngoài.
- Với mỗi truy vấn đếm số lượng, ta làm tương tự như trên và đếm số giá trị trong block bằng $\texttt{lazy}$.
Như vậy độ phức tạp mỗi truy vấn là $O(\sqrt{n})$ từ đó thu được thuật toán độ phức tạp $O(n\sqrt{n})$.
**Lưu ý.** Để lấy số lần xuất hiện của hash, bạn đọc nên tự cài hash map thay vì sử dụng `unordered_map` của C++.
chithanhnguyen
Created at
2 likes