【候选队互测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 [{tl}_{i} \dots {tr}_{i}]$ （ $S$ 的下标从 $1$ 开始）。

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

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

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

接下来的 $m$ 行，每行两个整数 ${tl}_{i}, {tr}_{i}$ 。

接下来的 $q$ 行，每行两个整数 ${ql}_{i}, {qr}_{i}$ 。

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

1
3

见附件下载。

子任务编号	$n ⩽$	$m ⩽$	$q ⩽$	特殊性质	分值
$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$ 的所有字符独立地在 `b` 和 `c` 中均匀随机生成	$20$
$4$	$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}$ 。

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

时间限制： $5s$

空间限制： $1GB$

Universal Online Judge