Bedan Contest #05 - C - Xâu đối xứng
Xem PDFCho xâu s gồm n kí tự, có q truy vấn cần thực hiện có dạng sau:
l r: Hãy kiểm tra có tồn tại một cặp số (i, j) nào thỏa mãn s_is_{i+1}...s_j là xâu đối xứng hay không (l \le i < j \le r).
Input and Output
Input
- Hai số nguyên dương n, q (1 \le n, q \le 10^5).
- Xâu s gồm n kí tự s_1s_2...s_n (s_i là chữ cái Latin thường).
- q dòng tiếp theo, dòng thứ i là truy vấn thứ i có dạng
l r(1 \le l \le r \le n).
Output
- Với mỗi truy vấn, hãy in ra
Yesnếu có vàNonếu ngược lại.
Test
Input
10 4
aabcbaddac
1 6
8 10
3 9
4 7
Output
Yes
No
Yes
No
Note
- Trong đoạn [1, 6], ta có cặp (2, 6) thỏa mãn vì
abcbalà xâu đối xứng. - Trong đoạn [8, 10], dễ dàng thấy không có cặp (i, j) nào thỏa mãn.
- Trong đoạn [3, 9], ta có cặp (7, 8) thỏa mãn vì
ddlà xâu đối xứng. - Trong đoạn [4, 7], dễ dàng thấy không có cặp (i, j) nào thỏa mãn.
Bình luận