Bedao Mini Contest 20 - Hardest Problem
Xem dạng PDF
Lihwy đang bận rộn chuẩn bị cho Bedao contest mới nhất. Lihwy có một danh sách các bài tập, được đánh dấu từ ~1~ đến ~n~. Ban đầu, các bài tập có độ khó là ~A_i = 0~. Tại ~q~ thời điểm sẽ có một trong hai việc sau xảy ra:
~1~ ~l~ ~r~ ~x~ ~(1 \le x \le 10^9)~: Với những bài tập ~i~ thoả mãn ~l \le i \le r~, Lihwy đã thêm thắt dữ kiện để bài tập đó trở nên khó hơn. Độ khó mới của bài tập thứ ~i~ luôn là ~A_i = A_i \oplus x~ với ~\oplus~ là phép toán xor.
~2~ ~l~ ~r~: Anh ấy muốn biết tổng xor độ khó của các bài tập trong đoạn ~[l, r]~. Nói cách khác, hãy tính giá trị ~A_l \oplus A_{l + 1} \oplus ... \oplus A_r~. Sau đó, do không hài lòng về kết quả, Lihwy sẽ xoá toàn bộ những dữ kiện thêm thắt của ~n~ bài tập. Lúc này độ khó tất cả các bài tập trở thành ~0~.
Hãy giúp Lihwy tính toán để Lihwy có thể chuẩn bị một contest Bedao chất lượng nhất nhé!
Input
Dòng đầu chứa hai số nguyên dương ~n~ và ~q~ ~(1 \le n, q \le 2 \times 10^5)~.
~q~ dòng tiếp theo chứa một trong hai sự việc.
Output
Với mỗi sự việc loại ~2~, in ra tổng độ khó cần tìm.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~50~ | ~n \le 100~ |
| 2 | ~50~ | không có giới hạn gì thêm |
Sample Input 1
3 4
1 1 3 1
2 1 3
1 1 2 2
2 2 2
Sample Output 1
1
2
Notes
Sau sự việc thứ nhất, độ khó các bài là ~[1, 1, 1]~. Do đó tổng xor độ khó đoạn ~[1, 3]~ là ~1~.
Sau sự việc thứ hai, độ khó tất cả các bài tập trở thành ~0~.
Sau sự việc thứ ba, độ khó các bài là ~[2, 2, 0]~. Tổng xor độ khó đoạn ~[2, 2]~ là ~2~.
Bình luận
Mình có một lời giải khác bằng lazy segmentree cho bài này
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.