You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

字符查询

题目描述

给定一个长度为 $n$ 的字符串 $s$，保证 $s$ 只包含小写字母。$q$ 次询问，每次询问指定一个区间 $[l,r]$ 与字符 $c$，求 $c$ 在 $s_{l\cdots r}$ 中出现了多少次。

输入格式

第一行两个整数 $n,q$。

接下来一行一个字符串 $s$。

接下来 $q$ 行，每行两个整数 $l,r$ 与一个字符 $c$，表示一次询问。

输出格式

$q$ 行，每行一个整数 $x$，表示 $c$ 在 $s_{l\cdots r}$ 中出现 $x$ 次。

5 2
abcda
1 5 a
2 2 b

2
1

数据范围与约定

对于 $30\%$ 的数据，$1\le n,q\le 10^3$。

对于 $100\%$ 的数据，$1\le n\le 10^6,1\le q\le 10^7$。

本题输入量较大，单数据点输入约 13MB，请选用较快速的读入方式。