Thách Thức Lập Trình Xuân Giáp Thìn - Lật sỏi
Xem dạng PDF
Trò chơi ô ăn quan truyền thống là một trò chơi truyền thống vô cùng quen thuộc với trẻ em Việt Nam. Tuy nhiên chúng ta sẽ đi đến phiên bản khác của trò chơi nhưng cũng cực trí tuệ: trò chơi lật sỏi.
Sân chơi gồm ~n~ vị trí trống từ vị trí ~0~ đến ~n - 1~. Mỗi hiệu lệnh được đưa ra, bạn sẽ nhận được ba số nguyên ~t, A, B~. Với mọi ~A ≤ i ≤ B~, nếu ~t = 0~ thì ta đổi trạng thái của vị trí thứ ~i~. Nếu ~t = 1~, ta cần đếm xem có bao nhiêu vị trí ~i~ đang có sỏi. Hãy nhanh tay trả lời các hiệu lệnh loại ~1~ nhé!
Nếu có thể nhanh tay đếm đúng số lượng sỏi thì bạn sẽ hoá thành một con rồng cừ khôi!
Input
Dòng thứ nhất gồm ~2~ số nguyên ~n~ và ~q~ ~(1 \le n, q \le 10^5)~ là số lượng hòn sỏi và số hiệu lệnh.
~q~ dòng tiếp theo, mỗi dòng gồm ~2~ loại hiệu lệnh:
Loại ~0~: ~0 \; A \; B~ với ~0 \le A \le B < n.~
Loại ~1~: ~1 \; A \; B~ với ~0 \le A \le B < n.~
Output
Gồm nhiều dòng, mỗi dòng là kết quả cho từng truy vấn loại ~2~.
Scoring
| Subtask | % số test | Giới hạn |
|---|---|---|
| 1 | ~50\%~ | ~n, q \le 5000~. |
| 2 | ~50\%~ | Không có điều kiện gì thêm. |
Sample Input 1
4 7
1 0 3
0 1 2
1 0 1
1 0 0
0 0 3
1 0 3
1 3 3
Sample Output 1
0
1
0
2
1
Notes
Giải thích test ví dụ:
Truy vấn thứ nhất, vì chưa có hòn sỏi nào, nên đáp án là ~0~.
Sau truy vấn thứ hai, các vị trí ~1, 2~ có sỏi.
Sau truy vấn thứ ba, vì chỉ có vị trí ~1~ có sỏi nên đáp án là ~1~.
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.