UOJ Logo Universal Online Judge

UOJ

#700. 【候选队互测2022】可爱多的字符串

附件下载 统计

有一次机灵鬼和学长可爱多打比赛, 可爱多不会做一道字符串题,机灵鬼做了很久终于做出来了,这是机灵鬼第一次做出可爱多不会的题。

可爱多觉得很丢人,于是准备研究字符串。可爱多精通 $\mathrm{kmp}$ 算法。$\mathrm{kmp}$ 算法的输入是一个字符串 $S$,该算法的核心是对每个 $i\in [1,n]$ 求出 $\mathrm{next}_i$,定义为: \begin{equation} \mathrm{next}_i = \max\{x\mid 0 \le x < i, S[1,x]=S[i-x+1,i]\} \end{equation} 其中 $S[l, r]$ 表示字符串 $S$ 中第 $l$ 个到第 $r$ 个字符组成的子串,如果 $r < l$ 则为空串。

他发现,如果 $i$ 向 $\mathrm{next}_i$ 连边,最后会形成一棵以 0 为根的树。他还注意到,如果一个串的 “循环度” 比较高的话,这颗树所有点的深度和就会比较大,比如 $\mathrm{aaaa}$ 的树的深度和是 1+2+3+4,$\mathrm{abab}$ 的深度和为 1+1+2+2,而 $\mathrm{abcd}$ 的深度和只有 1+1+1+1,他给这个树的深度和取了一个名字,叫做 $\mathrm{next}$ 树深度和。所以,可爱多遇到一个串就想算出他的 $\mathrm{next_i}$ 树深度和。

可爱多觉得仅仅算出一个串的 $\mathrm{next_i}$ 树深度和并不能体现出他高超的水平。于是,他给每个位置设置了一个喜爱度 $w_i$,现在他想计算 $\sum_{i=1}^n w_i\times \mathrm{dep}_i$,我们称之为带权 $\mathrm{next}_i$ 树深度和。可爱多经过很多练习过后,对带权 $\mathrm{next_i}$ 树深度和了如指掌,如果你告诉他一个长为 $n$ 的字符串 $S$,以及一个长为 $n$ 的数组 $W=\{w_1,w_2,\dots,w_n\}$,他可以立马告诉你这个串的带权 $\mathrm{next_i}$ 树深度。

现在机灵鬼给了可爱多一个长为 $n$ 的字符串 $S$ 供他研究,可爱多也设置好了 $n$ 个位置喜爱度。机灵鬼会多次取出字符串的一部分,即多次给出 $l,r$,他想让可爱多告诉他,当 $S'=S[l,r]$,$W'=\{w_l,w_{l+1},\dots,w_r\}$ 时,带权 $\mathrm{next}$ 树深度和。为了避免答案过大,答案对 $2^{32}$ 取模。

机灵鬼不想太为难可爱多,于是他给出的字符串字符集为 $\{0,1\}$。可爱多算不出来就会觉得很丢脸,于是请你帮帮他。

输入格式

第一行两个正整数 $n,m$ 表示字符串长度和询问个数。

第二行一个字符串,保证字符集为 $\{0,1\}$。

第三行 $n$ 个正整数 $w_i$ 表示每个位置的喜爱度。

接下来的 $m$ 行,每行两个数 $l,r$ 表示一个询问。保证 $1 \le l \le r \le n$。

输出格式

共 $m$ 行,每行一个整数表示答案。

样例一

input

10 10
1110110001
3 1 4 1 5 9 2 6 5 3 
6 9
1 5
4 6
5 10
6 8
3 9
7 9
9 10
6 6
6 9

output

22
28
15
42
17
48
29
8
9
22

样例二

见下发文件,这个样例满足子任务 5 的限制。

限制与约定

测试包编号 $n,m\le$ 特殊性质 分值 子任务依赖
1 $10^4$ 5
2 $10^5$ $w_i=1,r=n$ 10
3 $10^5$ $r=n$ 20 2
4 $10^5$ $w_i=1$,字符串的每个字符在 $\{0,1\}$ 中随机 10
5 $10^5$ 字符串的每个字符在 $\{0,1\}$ 中随机 10 4
6 $10^5$ $w_i=1$ 5 2,4
7 $10^5$ 20 1,3,5,6
8 $2\times 10^5$ 20 7

对于所有数据,有 $n,m\le 2\times 10^5,1\le w_i\le 10^9$。

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

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