QOJ.ac

QOJ

Time Limit: 5 s Memory Limit: 1024 MB Total points: 100
[+11]

# 5014. 复读程度

Statistics

题目描述

给定字符串 s[1,n] ,第 i 个字符被赋予两个权值:左权值 wli 和右权值 wri 。 

定义一个子串 s[l,r] 的左权值 vl(s[l,r]) 为: 其在原串中各个匹配的左端点的左权值 wl 和;右权值 vr(s[l,r]) 为: 其在原串中各个匹配的右端点的右权值 wr 和。这里 ts 中所有的 匹配是 1ijn,s[i,j]=t ,我们把这样的 ij 分别叫做一个匹配的左右端点。

定义一个子串 s[l,r] 的复读程度是它的左权值与右权值的乘积,即 w(s[l,r])=vl(s[l,r])vr(s[l,r])

q 次查询 l1,r1,l2,r2 ,令 S={(l,r)rlmax ,即以 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

样例输出

4
9
9
4
0

子任务

保证 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):无特殊限制。