Nguồn bài tập: AtCoder Regular Contest 092 - Problem B https://atcoder.jp/contests/arc092/tasks/arc092_b

Với mỗi ~k~ từ ~0~ đến ~20~, ta cần xác định xem bit thứ ~k~ của tổng ~XOR~ cần tìm là ~0~ hay ~1~ (nếu bit ~k~ là ~1~, ta sẽ cộng thêm ~2^k~ vào đáp án). Ta cần đếm số cặp ~(i,j)~ sao cho bit thứ ~k~ của ~a_i + b_j~ bằng ~1~. Nếu số cặp là chẵn thì bit thứ ~k~ của tổng ~XOR~ bằng ~0~, ngược lại thì bit thứ ~k~ của tổng ~XOR~ bằng ~1~.

Để thực hiện điều này, gọi ~T = 2^k~. Ta nhận xét rằng, ta chỉ cần quan tâm đến ~k + 1~ bit cuối của mỗi ~a_i~ và ~b_i~. Nói cách khác, ta chỉ cần quan tâm đến các giá trị ~a_i~ và ~b_i~ sau khi chua lấy dư cho ~2T~.

Ta nhận xét rằng, để bit thứ ~k~ của ~a_i + b_j~ bằng ~1~ thì giá trị ~a_i + b_j~ phải thỏa một trong hai điều kiện sau:

• ~T ≤ a_i + b_j < 2T~
• ~3T ≤ a_i + b_j < 4T~

Ta có thể đếm số cặp ~(i,j)~ sao cho ~a_i + b_j~ thỏa một trong hai điều kiện trên bằng cách: với mỗi giá trị ~a_i~, ta cần đếm số phần tử của mảng ~b~ thuộc một trong hai đoạn ~[T − a_i;2T − a_i − 1]~ và ~[3T −a_i;4T −a_i −1]~. Có thể thực hiện điều này trong ~O(logn)~ bằng cách chặt nhị phân (sau khi đã sắp xếp lại mảng ~b~ theo thứ tự tăng dần) hoặc trong ~O(1)~ bằng kĩ thuật mảng cộng dồn.

Độ phức tạp: ~O(nlognloga_i)~ hoặc ~O((n + a_i)loga_i)~