#P6788. [2019福建夏令营]大水题

    ID: 6609 传统题 1500ms 888MiB 尝试: 3 已通过: 1 难度: 9 上传者: 标签>难度分类省选/NOI-字符串AC 自动机失败链接贡献汇总数据结构懒标记线段树排序与序列处理一维前缀和CF2600

[2019福建夏令营]大水题

大水题

题目描述

给定 NN 个模式串 T1,T2,…,TNT_1,T_2,\ldots,T_N,以及一个字符串 SS。所有字符串均由小写英文字母组成。

依次执行 QQ 次操作,分为以下两种:

  • 1 l r str:把 SS 的区间 [l,r][l,r] 覆盖为 str 不断重复后的前 r−l+1r-l+1 个字符。每次重复都从本次修改的左端点 ll 开始对齐,SS 的总长度不变。例如,长度为 77 的区间用 abc 修改后变成 abcabca。
  • 2 l r:求所有模式串在当前子串 S[l,r]S_{[l,r]} 中出现的总次数。

每次修改都会影响之后的操作。查询只统计完全位于 [l,r][l,r] 中的匹配,允许不同匹配重叠;每个模式串、每个起始位置分别计数。若两个模式串内容相同,它们作为不同的 TiT_i 分别贡献次数。

输入格式

第一行两个整数 N,QN,Q,分别表示模式串个数和操作数。

接下来 NN 行,每行一个非空字符串 TiT_i,长度不超过 5050。保证把全部 TiT_i 插入一棵字典树后,字典树的大小不超过 5050。

接下来一行一个非空字符串 SS,长度不超过 100000100000。

接下来 QQ 行,每行描述一个操作,格式如上。其中 1≤l≤r≤∣S∣1\le l\le r\le|S|,修改串 str 非空。

输出格式

每个类型为 22 的操作输出一行一个整数,表示对应查询的总出现次数。

样例输入

2 5
aa
aba
aabaab
2 1 6
1 3 5 b
2 2 3
1 1 6 a
2 1 5

样例输出

3
0
4

数据范围与子任务

所有数据满足 N≤50N\le50,Q≤100000Q\le100000,∣S∣≤100000|S|\le100000,所有修改操作中 str 的长度总和不超过 ∣S∣|S|。所有字符串仅由小写英文字母组成。

子任务 分值 附加限制
1 1010 N≤1N\le1,Q≤200Q\le200,∣S∣≤5000\lvert S\rvert\le5000
2 N≤30N\le30,Q≤5000Q\le5000,∣S∣≤5000\lvert S\rvert\le5000
3 1515 N≤1N\le1,Q≤100000Q\le100000,∣S∣≤100000\lvert S\rvert\le100000
4 N≤30N\le30,Q≤60000Q\le60000,∣S∣≤60000\lvert S\rvert\le60000
5 5050 无