UOJ Logo Universal Online Judge

UOJ

#697. 【候选队互测2022】广为人知题

附件下载 统计

This problem might be well-known in some countries, but how do other countries learn about such problems if nobody poses them?

给定一个长度为 $n$ 的字符串 $S$,字符集为小写英文字母。

给定 $m$ 个模式串,第 $i$ 个为 $S[\mathrm{tl}_i \cdots \mathrm{tr}_i]$($S$ 的下标从 $1$ 开始)。

现有 $q$ 次查询,每次给出 $[\mathrm{ql}_i, \mathrm{qr}_i]$,求所有模式串在 $S[\mathrm{ql}_i \cdots \mathrm{qr}_i]$ 中的出现次数之和。

输入格式

第一行为三个整数 $n, m, q$。

第二行为一个长度为 $n$ 的字符串 $S$。

接下来的 $m$ 行,每行两个整数 $\mathrm{tl}_i, \mathrm{tr}_i$。

接下来的 $q$ 行,每行两个整数 $\mathrm{ql}_i, \mathrm{qr}_i$。

输出格式

$q$ 行,每行一个整数,依次表示每个查询的答案。

样例一

input

5 2 2
abaab
3 4
4 5
2 4
1 5

output

1
3

样例二

见附件下载。

数据范围

子任务编号 $n \leqslant $ $m \leqslant $ $q \leqslant $ 特殊性质 分值
$1$ $10^3$ $10^3$ $10^3$ $10$
$2$ $5 \times 10^4$ $10^5$ $5 \times 10^4$ $25$
$3$ $4 \times 10^5$ $10^6$ $10^5$ 保证 $S$ 的所有字符独立地在 bc 中均匀随机生成 $20$
$3$ $4 \times 10^5$ $10^6$ $10^5$ $45$

对于所有数据,$1 \leq n \leq 4 \times 10^5, 1 \leq m \leq 10^6, 1 \leq q \leq 10^5$。

提示

题目不一定按照难度顺序排列。

时间限制:$\texttt{5s}$

空间限制:$\texttt{1GB}$