Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Tewi đã ốm liệt giường nên Yagokoro Eirin phải chữa bệnh cho cô. Đoạn ADN của Tewi có độ dài n gồm cách kí tự a, b, c (vì sao thì chưa rõ). Eirin có thể sửa đổi một vị trí bất kì trên ADN với chi phí là 1.
Cô đang nghi ngờ q đoạn con [li, ri] có thể là nguyên nhân gây bệnh. Với mỗi đoạn ADN con này, Eirin muốn sửa lại đoạn này sao cho không tồn tại đoạn con nào có độ dài lớn hơn 1 là xâu đối xứng. Ví dụ aab là không thỏa mãn vì có aa là xâu đối xứng. Hãy giúp cô tính trước chi phí để chữa bệnh nhé!
Đầu vào
• Dòng đầu tiên gồm 2 số n, q.
• Dòng tiếp theo là một xâu gồm n kí tự chỉ gồm a, b, c.
• q dòng tiếp theo mỗi dòng gồm 2 số li, ri.
Đầu ra:
• q dòng là chi phí chữa bệnh.
Input:
5 4
baacb
1 3
1 5
4 5
2 3
Output:
1
2
0
1
Bình luận