字符频率检测系统

题目描述

某文本分析系统正在处理一段由小写英文字母组成的数据串。

系统记录了一段长度为 n 的字符串：

s

为了分析文本中特定字符的分布情况，系统会进行 q 次区间检测。

每次检测会给出两个整数：

l r

表示需要查看字符串中第 l 个字符到第 r 个字符组成的子串。

对于每一次检测，请统计：

在该子串中，字符 a 出现的次数。

注意：

• 字符位置从 1 开始编号；
• 查询区间包含第 l 个字符和第 r 个字符；
• 每次查询相互独立。

---

输入格式

第一行输入两个整数：

n q

其中：

• n 表示字符串长度；
• q 表示查询次数。

第二行输入一个长度为 n 的字符串：

s

字符串只包含小写英文字母。

接下来 q 行，每行输入两个整数：

l r

表示一次区间查询。

---

输出格式

对于每一次查询，输出一个整数：

表示字符串第 l 个字符到第 r 个字符中字符 a 的出现次数。

每个答案占一行。

---

数据范围

1 ≤ n ≤ 100000

1 ≤ q ≤ 100000

s 仅包含小写英文字母

1 ≤ l ≤ r ≤ n

---

输入样例

8 3
abacaaab
1 4
3 8
5 8

---

输出样例

2
4
3

---

样例解释

字符串：

a b a c a a a b

编号：

1 2 3 4 5 6 7 8

---

查询1

1 4

对应子串：

a b a c

其中：

a 出现 2 次

输出：

2

---

查询2

3 8

对应子串：

a c a a a b

其中：

a 出现 4 次

输出：

4

---

查询3

5 8

对应子串：

a a a b

其中：

a 出现 3 次

输出：

3

---

注意事项

1. 字符串长度可能很大，查询次数也可能很多。
2. 不建议每次查询重新扫描 l 到 r 的所有字符。
3. 注意区分：

字符串长度 n

和：

查询次数 q

4. 查询区间是闭区间：

[l,r]

包含左右端点。