Truy vấn K
Đề bài
Mô tả
Cho một dãy các quả bóng, mỗi quả có màu đen hoặc trắng. Ban đầu dãy có quả bóng. Bạn cần lần lượt thực hiện truy vấn. Ở mỗi truy vấn, gọi là số quả bóng trong dãy trước khi truy vấn diễn ra, và đánh số các quả bóng từ đến theo thứ tự từ trái sang phải. Mỗi truy vấn có một trong các dạng sau:
- I (, , là B hoặc W): chèn quả bóng màu vào dãy, ngay sau quả bóng thứ . Cụ thể:
- Nếu , các quả bóng được chèn vào đầu dãy.
- Nếu , các quả bóng được chèn vào giữa quả bóng thứ và quả bóng thứ .
- Nếu , các quả bóng được chèn vào cuối dãy.
- Nếu là B, mọi quả bóng được chèn đều màu đen; nếu là W, mọi quả bóng được chèn đều màu trắng.
- D (, ): xóa quả bóng liên tiếp khỏi dãy, bắt đầu từ quả bóng thứ .
- F (, ): đổi màu quả bóng liên tiếp bắt đầu từ quả bóng thứ . Nói cách khác, mỗi quả bóng đen được thay bằng một quả bóng trắng ở cùng vị trí, và ngược lại.
- Q (, ): chỉ xét quả bóng liên tiếp bắt đầu từ quả bóng thứ , chia chúng thành ít đoạn nhất sao cho mỗi đoạn gồm các quả bóng liên tiếp cùng màu, và gọi là độ dài các đoạn này. Hãy tính và in ra giá trị . Lưu ý rằng cách chia này luôn là duy nhất.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên và .
- Dòng thứ hai chứa ký tự B hoặc W, mô tả màu của các quả bóng trong dãy ban đầu (B là đen, W là trắng).
- dòng tiếp theo, mỗi dòng chứa một truy vấn theo mô tả ở trên.
Dữ liệu ra
Với mỗi truy vấn dạng Q , in ra kết quả trên một dòng. Vì kết quả có thể rất lớn, hãy in ra phần dư khi chia cho .
Ràng buộc
- .
- Các tham số của truy vấn thỏa mãn các ràng buộc nêu ở trên.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 8 2 WWWBBWWW Q 1 2 Q 2 6 |
4 12 |
Dãy không đổi. Truy vấn thứ nhất xét WW, chỉ có một đoạn, kết quả là . Truy vấn thứ hai xét WWBBWW, gồm ba đoạn: bóng trắng, bóng đen và bóng trắng, kết quả là . |
| 5 7 BBWBB Q 2 3 I 0 3 B Q 3 4 F 4 3 Q 4 2 D 4 2 Q 1 6 |
3 10 4 36 |
Ban đầu dãy là BBWBB. Truy vấn thứ nhất xét BWB, gồm ba đoạn một bóng, kết quả là . Sau truy vấn thứ hai, dãy là BBBBBWBB. Truy vấn thứ ba xét BBBW: . Sau truy vấn thứ tư, dãy là BBBWWBBB. Truy vấn thứ năm xét WW: . Sau truy vấn thứ sáu, dãy là BBBBBB. Truy vấn cuối xét cả dãy: . |
Bình luận