复读程度 - Problem

题目描述

给定字符串 $s[1, n]$ ，第 $i$ 个字符被赋予两个权值：左权值 $w l_i$ 和右权值 $w r_{i \text { 。 }}$

定义一个子串 $s[l, r]$ 的左权值 $v l(s[l, r])$ 为: 其在原串中各个匹配的左端点的左权值 $w l$ 和；右权值 $v r(s[l, r])$ 为: 其在原串中各个匹配的右端点的右权值 $w r$ 和。这里 $t$ 在 $s$ 中所有的匹配是 $\forall 1 \leq i \leq j \leq n, s[i, j]=t$ ，我们把这样的 $i$ 和 $j$ 分别叫做一个匹配的左右端点。

定义一个子串 $s[l, r]$ 的复读程度是它的左权值与右权值的乘积，即 $w(s[l, r])=v l(s[l, r]) \cdot v r(s[l, r])$ 。

$q$ 次查询 $l_1, r_1, l_2, r_2$ ，令 $S=\left\{(l, r) \mid r-l \geq \max \left\{r_1-l_1, r_2-l_2\right\}, s\left[l, l+r_1-l_1\right]=s\left[l_1, r_1\right], s\left[r-r_2+l_2, r\right]=s\left[l_2, r_2\right]\right\}$ ，即以 $S$ 为所有满足 $s\left[l_1, r_1\right]$ 为 $s[l, r]$ 的前缀， $s\left[l_2, r_2\right]$ 为 $s[l, r]$ 的后缀的 $(l, r)$ 的集合。求 $\sum_{(l, r) \in S} w(s[l, r])$ 。

由于答案很大，你只需要输出答案对 $2^{64}$ 取模后的结果。

输入格式

第一行两个正整数 $n, q$ ，表示字符串长度与查询次数。

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

第三行 $n$ 个整数 $w l_i$ 表示左权值。

第四行 $n$ 个整数 $w r_i$ 表示右权值。

接下来 $q$ 行，每行给出四个整数 $l_1, r_1, l_2, r_2$ ，表示一次查询。

输出格式

$q$ 行，第 $i$ 行输出第 $i$ 次查询的答案对 $2^{64}$ 取模后的结果。

样例数据

样例输入

6 5
ababcc
1 1 1 1 1 1
1 1 1 1 1 1
1 1 5 5
3 4 1 2
1 1 2 2
1 2 6 6
5 5 1 2

样例输出

子任务

保证 $1 \leq n, q \leq 10^5, 0 \leq w l_i, w r_i < 2^{64}, 1 \leq l_1 \leq r_1 \leq n, 1 \leq l_2 \leq r_2 \leq n ， s$ 仅有小写字母构成。

subtask1(7pts)：保证 $n, q \leq 500$ 。
subtask2(15pts)：保证 $n, q \leq 5000$ 。
subtask3(12pts)：保证 $n \leq 5000$ 。
subtask4(6pts): 保证 $l_1=1$ ，且对任意 $2 \leq i \leq n$ ，有 $s_1 \neq s_i$ 。
subtask5(16pts)：保证 $s\left[l_1, r_1\right]$ 在 $s$ 中最多出现 5 次。
subtask6(21pts)：保证 $n, q \leq 5 \times 10^4$ 。
subtask7(23pts)：无特殊限制。

QOJ.ac

QOJ