#549. 【2024-11-22 P3】C - 串串

【2024-11-22 P3】C - 串串

C - 串串

题目描述

定义 occ(s,t)occ(s,t) 为 tt 在 ss 中出现的次数,例如 occ(ababa,aba)=2occ(ababa,aba)=2 。

定义 S[l:r]S[l:r] 代表 Sl,Sl+1,…,SrS_l,S_{l+1},\dots,S_r 连接形成的字符串。

现在给定长度为 nn 的串 S,TS,T 以及长度为 nn 的序列 ww 。

定义 f(t)=∑i=1nwi∗occ(t,S[1:i])f(t)=\sum\limits_{i=1}^n w_i*occ(t,S[1:i]) 。

现在有 mm 次询问,每次询问给定 l,rl,r ,你需要求出f(T[l:r])f(T[l:r]) 的值。

输入格式

第一行一个整数 n,mn,m ,分别代表串的长度,以及询问的个数。

第二行一个长度为 nn 的字符串表示 SS 。

第三行一个长度为 nn 的字符串表示 TT 。

第四行包含 nn 个整数,第 ii 个整数代表 wiw_i 。

接下来 mm 行,每行包含两个整数 l,rl,r ,表示一次询问的信息。

输出格式

输出包含 mm 行,第 ii 行表示第 ii 次询问的答案。

样例

样例输入

8 5
abbabaab
aababbab
1 2 4 8 16 32 64 128
1 1
2 3
3 5
4 7
1 8

样例输出

1
3
3
16
38

数据范围

对于所有数据,$1\le n,m\le 4*10^5,1\le w_i\le 10^4,1\le l\le r\le n$ 。

子任务 1 ( 15% ) : 1≤n,m≤3001\le n,m\le 300 。

子任务 2 ( 15% ) : 1≤n,m≤30001\le n,m\le 3000 。

子任务 3 ( 20% ) :r=nr=n 。

子任务 4 ( 20% ) :1≤n,m≤500001\le n,m\le 50000 。

子任务 5 ( 20% ) :1≤n,m≤2∗1051\le n,m\le 2*10^5 。

子任务 6 ( 10% ) : 无特殊限制。