#P9041. [2017年备战省选]字符串

    ID: 9247 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2400提高+/省选-后缀自动机按长度传播出现次数根号分治二分查找树上倍增

[2017年备战省选]字符串

题目描述

给定字符串 ss、mm 个区间 [li,ri][l_i,r_i] 和整数 kk。记 w[l,r]w[l,r] 为字符串 ww 的下标区间 [l,r][l,r] 对应的子串,字符串下标从 00 开始。记 f(s,w,l,r)f(s,w,l,r) 为 w[l,r]w[l,r] 在 ss 中出现的次数。

每个询问给定长度为 kk 的字符串 ww 和两个整数 a,ba,b,求

∑i=abf(s,w,li,ri).\sum_{i=a}^{b} f(s,w,l_i,r_i).

区间编号也从 00 开始。例如,若 s=ababas=\texttt{ababa},w=abaw=\texttt{aba},则 f(s,w,0,2)=2f(s,w,0,2)=2。

输入格式

第一行四个整数 n,m,q,kn,m,q,k,其中 nn 是 ss 的长度,qq 是询问数。

第二行一个长度为 nn 的字符串 ss。

接下来 mm 行,每行两个整数 li,ril_i,r_i。之后 qq 行,每行一个字符串 ww 和两个整数 a,ba,b。

输出格式

每个询问输出一行一个整数,表示答案。

样例

8 5 3 3
abacdaba
0 2
1 2
0 0
2 2
1 2
dab 1 4
bac 2 3
eeb 1 3
7
3
2

数据范围

  • 对于 10%10\% 的数据,n,m,k,q≤10n,m,k,q\le10。
  • 对于 30%30\% 的数据,n,m,k,q≤102n,m,k,q\le10^2。
  • 原题对 50%50\% 和所有数据均列出 n,m,k,q≤104n,m,k,q\le10^4。
  • 对于所有数据,询问字符串的总长度不超过 10510^5,字符串均由小写英文字母组成。

原 PDF 题面