Editorial for Bedao Regular Contest 13 - XORQRY
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Ta sẽ xử lý các truy vấn theo chiều ~r~ tăng dần.
Với mỗi phần tử từ ~1~ tới ~i~, ta sẽ lưu vị trí xuất hiện cuối cùng của nó. Ví dụ: nếu ta xử lý đến ~[3, 2, 1, 1, 3]~, ta sẽ lưu lại thành ~[0, 2, 0, 1, 3]~.
Sau đó, để trả lời truy vấn ~(l, i)~, ta chỉ cần lấy phép ~\text{xor}~ các số trong đoạn ~[l..i]~. Cả hai thao tác cập nhật và trả lời truy vấn đều có thể xử lý bằng fenwick tree.
Độ phức tạp: ~O((n + q)\ \text{log}\ n)~.
Comments
Đọc hổng hiểu ad ghi cụ thể hơn đi ad ạ :((