Gương Soi Chữ Cái
Points
52
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Đề bài
Cho xâu S gồm N chữ cái thường. Có hai thao tác: đổi một ký tự, hoặc kiểm tra xâu con S[l..r] có phải xâu đối xứng (palindrome) hay không. Gợi ý: dùng cây đoạn lưu hash xuôi và hash ngược.
Dữ liệu vào
Dòng đầu chứa N và Q. Dòng thứ hai là xâu S. Q dòng tiếp theo:
1 i c: đổi S_i thành chữ cái c.2 l r: kiểm tra.
Dữ liệu ra
Với mỗi truy vấn loại 2, in YES nếu S[l..r] là xâu đối xứng, ngược lại in NO.
Ví dụ
| Input | Output |
|---|---|
| 5 4\nbabab\n1 4 c\n1 1 b\n2 1 5\n1 4 a | NO |
Giới hạn
- 1 ≤ N, Q ≤ 10^5
- S chỉ gồm chữ cái thường 'a'..'z'
Community Discussion