Kiểm tra đối xứng động
Points
40
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề 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 raYESnếu đúng, ngược lại in raNO.
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 choặc2 l r.
Dữ liệu ra
- Với mỗi truy vấn loại
2, in raYEShoặcNOtrê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$
Community Discussion