Truy Vấn Đếm Palindrome Trong Đoạn
Points
85
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
string
Đề bài
Cho chuỗi $S$ gồm $N$ ký tự in thường và $Q$ truy vấn. Mỗi truy vấn gồm hai số nguyên $L$ và $R$ ($1$-indexed), hãy đếm số lượng chuỗi con đối xứng (palindrome) nằm hoàn toàn trong đoạn $S[L..R]$.
Hai chuỗi con ở vị trí khác nhau được tính là khác nhau.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N$ và $Q$.
- Dòng thứ hai chứa chuỗi $S$ có độ dài $N$.
- $Q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $L$ và $R$.
Dữ liệu ra
- Với mỗi truy vấn, in ra số lượng chuỗi con đối xứng trong đoạn $S[L..R]$.
Ví dụ
| Input | Output |
|---|---|
| 5 3\nabcba\n1 5\n1 3\n2 4 | 7\n4\n4 |
Giới hạn
- $1 \le N \le 3000$
- $1 \le Q \le 10^5$
- $1 \le L \le R \le N$
- Chuỗi chỉ chứa ký tự in thường từ
ađếnz.
Giải thích ví dụ 1: Truy vấn 1 ($S[1..5] = $ abcba): palindromes là a, b, c, b, a, bcb, abcba → 7.
Community Discussion