Chữa bệnh

Xem dạng PDF

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

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.