Bedao Mini Contest 20 - Hardest Problem
View as 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~.
Comments
This comment is hidden due to too much negative feedback. Show it anyway.