CSES - Palindrome Queries | Truy vấn xâu đối xứng
Xem PDF
Điểm:
2000 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Bạn được cho một xâu bao gồm \(n\) kí tự giữa a - z. Các vị trí của xâu được đánh số \(1, 2, \ldots, n\).
Nhiệm vụ của bạn là xử lý \(m\) thao tác thuộc các loại sau:
- Thay đổi kí tự ở vị trí \(k\) thành \(x\).
- Kiểm tra xâu con từ vị trí \(a\) đến vị trí \(b\) có phải là xâu đối xứng hay không.
Input
- Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(m\): độ dài của xâu và số lượng thao tác.
- Dòng tiếp theo có một xâu bao gồm \(n\) kí tự.
- Cuối cùng, có \(m\) dòng mô tả các thao tác. Mỗi dòng có dạng
1 k xhoặc2 a b.
Output
- Đối với mỗi thao tác \(2\), in
YESnếu xâu con là một xâu đối xứng vàNOnếu ngược lại.
Constraints
- \(1 \leq n, m \leq 2 \cdot 10^5\)
- \(1 \leq k \leq n\)
- \(1 \leq a \leq b \leq n\)
Example
Test 1
Input
7 5
aybabtu
2 3 5
1 3 x
2 3 5
1 5 x
2 3 5
Output
YES
NO
YES
Bình luận
có cách nào mà không kiểm tra đối xứng không ạ
hoặc kiểm tra đối xứng nhanh k ạ
Sử dụng Hash + Segment Tree nha
hash thì mik kt oke, nhưng mà hash+SMT thì lm thế nào v???