Bedan Contest #05 - C - Xâu đối xứng

View as PDF

Submit solution


Points: 900
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem types

Cho 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 Yes nếu có và No nế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ì abcba là 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ì dd là 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.

Comments

There are no comments at the moment.