Gương Soi Chữ Cái

Buổi 27 — Segment Tree cơ bản
Points
52
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Submissions
Đề 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'
Draft saved