Làm đẹp xâu
Đề bài
Mô tả
FWMC nhận được một xâu độ dài , gồm các ký tự , làm quà sinh nhật. Ban đầu, mọi ký tự trong đều là chữ cái A.
Sau đó FWMC bắt đầu nghịch xâu này. Quá trình được mô tả bằng một dãy truy vấn, mỗi truy vấn thuộc một trong hai loại sau:
- 1 l r c: FWMC gán ký tự cho mọi vị trí trong đoạn (tức là đặt với mọi ).
2 k: FWMC không thích những dãy dài các ký tự giống nhau liên tiếp. FWMC coi một xâu là tốt nếu không có xâu con liên tiếp nào gồm nhiều hơn ký tự giống nhau. Với xâu hiện tại, FWMC muốn biết số ký tự ít nhất cần xóa để trở thành xâu tốt.
Lưu ý rằng FWMC chỉ muốn biết số ký tự ít nhất cần xóa, chứ không thực sự thay đổi .
Nhiệm vụ của bạn là giúp FWMC trả lời mọi truy vấn loại thứ hai.
Một xâu là xâu con liên tiếp của xâu nếu nhận được từ bằng cách xóa một số (có thể là không hoặc tất cả) ký tự ở đầu và một số (có thể là không hoặc tất cả) ký tự ở cuối.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên và (): độ dài xâu và số truy vấn.
Mỗi dòng trong dòng tiếp theo mô tả một truy vấn. Số nguyên đầu tiên là (): loại truy vấn.
- Nếu : tiếp theo là hai số nguyên và () và một chữ cái Latin in hoa .
- Nếu : tiếp theo là một số nguyên ().
Dữ liệu ra
Với mỗi truy vấn loại thứ hai, in ra một số nguyên: số ký tự ít nhất cần xóa để xâu trở thành xâu tốt.
Ràng buộc
- .
- , là chữ cái Latin in hoa.
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 11 10 1 0 1 F 1 2 10 C 1 3 8 W 1 9 9 M 1 4 6 M 2 2 2 1 2 5 1 5 7 C 2 1 |
1 4 0 3 |
Năm truy vấn đầu biến đổi xâu: AAAAAAAAAAA → FFAAAAAAAAA → FFCCCCCCCCC → FFCWWWWWWCC → FFCWWWWWWMC → FFCWMMMWWMC. Truy vấn 6 (): xóa một ký tự được FFCWMMWWMC, các nhóm FF, C, W, MM, WW, M, C đều không quá 2 ký tự. Truy vấn 7 (): xóa 4 ký tự, ví dụ được FCWMWMC, không thể xóa ít hơn. Truy vấn 8 (): xâu đã tốt. Truy vấn 9 biến xâu thành FFCWMCCCWMC; truy vấn 10 (): xóa 3 ký tự, ví dụ được FCWMCWMC. |
| 12 5 1 3 7 G 1 7 11 G 1 4 5 C 1 0 6 C 2 2 |
8 | Xâu cuối cùng là CCCCCCCGGGGG: nhóm 7 chữ C và nhóm 5 chữ G, cần xóa ký tự. |
Bình luận