Kiểm tra đối xứng động

Buổi 77 — Tổng kết Strings
Points
40
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Cho một xâu $S$ độ dài $N$ chỉ gồm các chữ cái tiếng Anh viết thường (a–z), đánh số từ $1$ đến $N$. Thực hiện $Q$ truy vấn thuộc một trong hai loại:

  • 1 i c: Đổi ký tự tại vị trí $i$ thành ký tự $c$.
  • 2 l r: Kiểm tra xem xâu con $S[l..r]$ có phải là xâu đối xứng (palindrome) hay không. In ra YES nếu đúng, ngược lại in ra NO.
Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N, Q$ ($1 \le N, Q \le 10^5$).
  • Dòng thứ hai là xâu $S$ độ dài $N$.
  • $Q$ dòng tiếp theo, mỗi dòng là một truy vấn dạng 1 i c hoặc 2 l r.
Dữ liệu ra
  • Với mỗi truy vấn loại 2, in ra YES hoặc NO trên một dòng.
Ví dụ
Input Output
5 4
ababa
2 1 5
1 2 c
2 1 5
2 3 5
YES
NO
YES
Giới hạn
  • $1 \le N, Q \le 10^5$
  • $1 \le l \le r \le N$
Draft saved