Chọn ĐTQG Gia Lai 2026 - Tổng XOR
Xem dạng PDFTrong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Cho dãy ~n~ số nguyên ~a_1, a_2, \dots, a_n~. Có hai loại thao tác trên dãy được mô tả như sau:
1 ~i~ ~x~: thay số thứ ~i~ bằng giá trị ~x~.
2 ~L~ ~R~: ~(1 \le L \le R \le n)~, với mọi ~u, v~ thỏa mãn điều kiện ~L \le u \le v \le R~, tính XOR các phần tử có thứ tự ~u~ đến ~v~, sau đó tính tổng tất cả các kết quả phép XOR.
Yêu cầu: Hãy xác định tổng tất cả các phép XOR sau mỗi thao tác loại ~(2)~.
Input
Dòng đầu tiên chứa ~2~ số nguyên ~n~ và ~m~ ~(1 \le n, m \le 10^5)~.
Dòng thứ ~2~ chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(0 \le a_i \le 10^8;\ 1 \le i \le n)~.
Mỗi dòng trong ~m~ dòng sau chứa ~3~ số nguyên mô tả một loại thao tác, có định dạng:
1 ~i~ ~x~: thao tác loại ~(1)~ ~(1 \le i \le n;\ 0 \le x \le 10^8)~.
2 ~L~ ~R~: thao tác loại ~(2)~ ~(1 \le L \le R \le n)~.
Các số trên cùng dòng được ghi cách nhau một dấu cách.
Output
Các kết quả sau mỗi thao tác loại ~(2)~, mỗi kết quả trên một dòng.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~20\%~ | ~1 \le n, m \le 10^2~. |
| 2 | ~40\%~ | ~10^2 < n, m \le 10^4~. |
| 3 | ~40\%~ | Không có giới hạn gì thêm. |
Sample Input 1
4 3
1 1 2 2
1 3 4
2 1 3
2 2 4
Sample Output 1
15
25
Notes
Dãy ban đầu là ~1, 1, 2, 2~. Sau thao tác thứ nhất (1 3 4) thì dãy trở thành ~1, 1, 4, 2~.
Với thao tác thứ hai (2 1 3), ta tính được mọi cặp ~(u, v)~ thỏa ~L \le u \le v \le R~ ~(L = 1, R = 3)~ như sau:
| ~u~ | ~v~ | XOR các phần tử trong đoạn ~[u \dots v]~ | Ghi chú |
|---|---|---|---|
| ~1~ | ~1~ | ~1~ | Trong đoạn ~[1 \dots 1]~ chỉ có ~1~ phần tử ~a[1] = 1~, nên kết quả là ~1~. |
| ~1~ | ~2~ | ~0~ | Trong đoạn ~[1 \dots 2]~ có ~2~ phần tử ~a[1] = 1~, ~a[2] = 1~; ~a[1] \operatorname{XOR} a[2] = 1 \operatorname{XOR} 1 = 0~. |
| ~1~ | ~3~ | ~4~ | Trong đoạn ~[1 \dots 3]~ có ~3~ phần tử ~a[1] = 1~, ~a[2] = 1~, ~a[3] = 4~; ~a[1] \operatorname{XOR} a[2] \operatorname{XOR} a[3] = 1 \operatorname{XOR} 1 \operatorname{XOR} 4 = 0 \operatorname{XOR} 4 = 4~. |
| ~2~ | ~2~ | ~1~ | Trong đoạn ~[2 \dots 2]~ chỉ có ~1~ phần tử ~a[2] = 1~, nên kết quả là ~1~. |
| ~2~ | ~3~ | ~5~ | Trong đoạn ~[2 \dots 3]~ có ~2~ phần tử ~a[2] = 1~, ~a[3] = 4~; ~a[2] \operatorname{XOR} a[3] = 1 \operatorname{XOR} 4 = 5~. |
| ~3~ | ~3~ | ~4~ | Trong đoạn ~[3 \dots 3]~ chỉ có ~1~ phần tử ~a[3] = 4~, nên kết quả là ~4~. |
| Tổng | ~15~ |
- Với thao tác thứ ba (2 2 4), ta thực hiện tương tự, thu được kết quả là ~25~.
Ghi chú: phép toán XOR trong C++ và Python dùng dấu ^, còn Pascal viết là xor. Ví dụ: ~5~ (dãy bit 101) XOR với ~3~ (dãy bit 011) cho kết quả bằng ~6~ (dãy bit 110).
Bình luận