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.

Author: bedao

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

Please read the guidelines before commenting.



  • 0
    DQX1938  commented on March 16, 2023, 6:06 p.m.

    Đọc hổng hiểu ad ghi cụ thể hơn đi ad ạ :((