XOR đoạn
Xem dưới dạng PDF
Gửi bài giải
Điểm:
100
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
đầu vào:
stdin
Đầu ra:
stdout
Tác giả:
Kiểu bài tập
Tèo có một dãy số \(a_1, a_2, ..., a_N\). Có \(Q\) câu hỏi, mỗi câu hỏi cho hai số \(L\) và \(R\) và yêu cầu tính:
\(a_L \oplus a_{L+1} \oplus ... \oplus a_R\)
Trong đó \(\oplus\) là phép XOR (exclusive or) trên bit.
Hãy giúp Tèo trả lời nhanh các câu hỏi.
Ràng buộc
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | 30 | Các giá trị nhỏ |
| 2 | 30 | \(N \le 10^5\) |
| 3 | 40 | Không có ràng buộc gì thêm |
Dữ liệu
- Dòng đầu: \(N\) và \(Q\)
- Dòng thứ hai: \(N\) số nguyên \(a_1, a_2, ..., a_N\)
- \(Q\) dòng tiếp theo, mỗi dòng gồm \(L\) và \(R\)
Kết quả
Với mỗi câu hỏi, in ra kết quả trên một dòng.
Giới hạn
| Mức | \(N, Q\) | Điểm |
|---|---|---|
| 1 | \(\le 10\) | 20 |
| 2 | \(\le 100\) | 20 |
| 3 | \(\le 10^4\) | 30 |
| 4 | \(\le 10^5\) | 30 |
Nhận xét