**LỜI GIẢI**
Với $S$ là [mảng cộng dồn](https://wiki.vnoi.info/algo/data-structures/prefix-sum-and-difference-array.md) của mảng $A$, ta có $A_l + A_{l + 1} + \dots + A_r = S_r - S_{l - 1}$ và mỗi mệnh đề $(l, r, t)$ trở thành $S_r - S_{l - 1} \equiv t \pmod{2}$. Dễ thấy luôn dựng lại được mảng $A$ từ mảng $S$ bằng $A_i = S_i - S_{i-1}$ nên ta chỉ quan tâm có dựng được mảng $S$ mà không bị mâu thuẫn về tính chẵn lẻ hay không.
Ta xử lí lần lượt từng mệnh đề: nếu mệnh đề thứ $i$ làm cho $S_{l_i - 1}$ hoặc $S_{r_i}$ vừa chẵn vừa lẻ thì $i - 1$ là kết quả (nếu xử lí được hết các mệnh đề mà không bị mâu thuẫn thì $q$ là kết quả), ngược lại ta sử dụng **DSU** để "lưu lại" mệnh đề thứ $i$ vào một đồ thị logic như sau:
> Mỗi đỉnh $u$ thể hiện mệnh đề $S_u$ chẵn và đỉnh $u^{\*}$ thể hiện mệnh đề $S_u$ lẻ (Lưu ý cần bao gồm cả hai đỉnh $0$ và $0^{\*}$ vì ta không nhất thiết phải gán cứng $S_0 = 0$).
> Giữa hai đỉnh có cạnh nối khi và chỉ khi chúng thể hiện hai mệnh đề tương đương. Suy ra hai đỉnh liên thông thì cũng thể hiện hai mệnh đề tương đương.
> Mảng $S$ mâu thuẫn khi đồ thị có một đỉnh $u$ nào đó liên thông với đỉnh $u^{\*}$.
Với mỗi mệnh đề $(l, r, t)$, giả sử $t = 0$, ta có $S_r \equiv S_{l - 1} \pmod{2}$ nên nếu $S_r$ chẵn thì $S_{l - 1}$ cũng chẵn và ngược lại. Do đó, ta nối hai cạnh $(r, (l - 1))$ và $(r^{\*}, (l - 1)^{\*})$, rồi kiểm tra lần lượt từng cặp hai đỉnh $r, r^{\*}$ và $(l - 1), (l - 1)^{\*}$ có cùng thuộc một TPLT hay không. Trường hợp $t = 1$ làm tương tự.
sasaki2c
Created at
0 likes