Đếm ký tự trong đoạn xâu

Buổi 15 — Prefix Sum & Difference Array prefix-sum Strings
Points
20
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
array1d
Submissions
Đề bài

Cho một xâu ký tự $S$ chỉ gồm các chữ cái tiếng Anh viết thường (a–z), đánh số ký tự từ $1$ đến $|S|$. Có $Q$ truy vấn, mỗi truy vấn gồm hai chỉ số $L, R$ và một ký tự $c$, yêu cầu đếm số lần xuất hiện của $c$ trong đoạn xâu từ vị trí $L$ đến $R$.

Dữ liệu vào

Dòng đầu chứa xâu $S$ và số nguyên $Q$, cách nhau bởi dấu cách. $Q$ dòng tiếp theo, mỗi dòng chứa $L, R$ và ký tự $c$.

Dữ liệu ra

Với mỗi truy vấn, in ra số lần xuất hiện của ký tự $c$ trên một dòng.

Ví dụ
Input Output
abacaba 3
1 7 a
2 5 b
1 4 c
4
1
1
hello 2
1 5 l
1 3 z
2
0
Giới hạn

$1 \le |S|, Q \le 10^5$, $1 \le L \le R \le |S|$.

Draft saved