UOJ Logo Universal Online Judge

UOJ

#752. 【UNR #6】Border 的第五种求法

附件下载 统计

在下山市停留的最后一天,为了纪念他们参加的最后一次 UOI,hehe 蚤决定和 he_____he 蚤一起去酒馆喝酒。

出人意料的是,他们在酒馆看到了孔乙己。在下单的时候,孔乙己凑了上来,对 hehe 蚤说:“你学过 OI 吗?” hehe 蚤点一点头。孔乙己说,“学过 OI,……我便考你一考。border 的四种求法,怎样做的?” hehe 蚤想,这本是字符串中极入门的题目,便懒懒的答他道,“不就是建 SAM 后扫描线树剖线段树吗?”孔乙己显出极高兴的样子,点头说,“对呀对呀!这题还有第二种做法,还可以求出基本子串字典,你知道吗?”

he_____he 蚤听到后起了兴致,反问孔乙己道:“你知道 border 的第五种求法吗?考你一考,这题怎样做的?”。he_____he 蚤边说边用手指蘸了水,在柜台上写下了题面。

但这下不仅孔乙己被难住了,连 hehe 蚤也陷入了沉思。你能帮他们解决 he_____he 蚤的题目吗?

题目描述

如果一个字符串 $t_1$ 是另一个字符串 $t_2$ 的前缀,同时也是 $t_2$ 的后缀,那么我们称 $t_1$ 是 $t_2$ 的一个 border(边界)。

例如,字符串 $\texttt{abacaba}$ 的 border 有:$\texttt{a}$, $\texttt{aba}$, $\texttt{abacaba}$。

为了展示 border 的第五种求法,he_____he 蚤给定了一个长度为 $n$ 的字符串 $s$ 和一个数组 $f_1, \dots, f_n$。

如果一个字符串 $t$ 在 $s$ 中出现了至少一次,那么我们定义 $t$ 的价值为 $f_{c}$,其中 $c$ 是 $t$ 在 $s$ 中的出现次数。

例如,字符串 $\texttt{abacaba}$ 中,$\texttt{aba}$ 出现了两次,价值为 $f_2$。

现有 $q$ 次询问,每次询问会给出一个区间 $[l, r]$。对于每个询问区间 $[l, r]$,你需要输出字符串 $s_l s_{l+1} \cdots s_r$ 的所有 border 的价值之和。即,取出 $s$ 在区间 $[l, r]$ 内的所有字符,拼成一个字符串;找出该串的所有 border,求出每个 border 的价值,然后求和。

所有 $f_i$ 的值在输入中给出。

输入格式

第一行两个正整数 $n,q$ ,表示 $s$ 的长度与询问次数。

第二行一个由小写字母构成的字符串 $s$ 。

第三行 $n$ 个数 $f_1,f_2,\ldots,f_n$ 。

接下来 $q$ 行,每行两个正整数 $l,r$ ,表示一次查询。

输出格式

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

样例一

input

5 4
ababa
1 2 3 4 5
2 3
2 4
1 4
1 5

output

2
3
3
6

explanation

对 $l=1,r=5$ 的询问,三个 border 分别为 $\texttt{a},\texttt{aba},\texttt{ababa}$ ,对应的在原串中的出现次数分别为 $3,2,1$ ,所以答案为 $f_3+f_2+f_1=3+2+1=6$ 。

样例二

见附件下载。该样例满足子任务 2 的限制。

样例三

见附件下载。该样例满足子任务 3 的限制。

数据范围

对于所有数据,保证 $1 \leq n, q \leq 5\times 10^5,1\leq l\leq r\leq n,1\leq f_i\leq 10^9$ ,保证 $s$ 由小写字母构成。

子任务编号 $n,q \leq$ 特殊性质 分值
$1$ $5\times 10^3$ $10$
$2$ $5\times 10^5$ A $10$
$3$ $10^5$ B $25$
$4$ $10^5$ $15$
$5$ $5\times 10^5$ $40$

特殊性质 A:保证 $s$ 的每个字符均从 $\texttt{a}$ 和 $\texttt{b}$ 中等概率独立随机生成。

特殊性质 B:保证 $\forall 1\leq i\leq n, f_i=i$ 。

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

空间限制:$1200\texttt{MB}$

后记

本在一旁慢慢喝酒的小 d 听到了 he_____he 蚤的题目,三下五除二就秒杀了,起身走过来教育了 hehe 蚤和孔乙己。

在欢声笑语中,这一次旅程终于画上了句点。也许他们中的每一个人都永远不会忘记这一天。