#P18181. Generated String
Generated String
Generated String
给定一个长度为 的模板字符串 。选择若干个非空子串,并按给出的顺序连接,可以得到一个生成字符串。
具体地,一个生成字符串由正整数 和 对下标 描述:
$$f\bigl(k,(l_1,r_1),\ldots,(l_k,r_k)\bigr) =S[l_1:r_1]+\cdots+S[l_k:r_k].$$这里 ,加号表示字符串连接。各片段可以重叠、重复,片段之间不要求按模板下标递增排列。
维护一个初始为空的字符串多重集 ,依次执行以下 个操作:
+ k l1 r1 ... lk rk:将这些片段描述的生成字符串插入 。- t:删除第 个操作插入的那个字符串实例。保证第 个操作是插入,且该实例目前尚未被删除。? k l1 r1 ... lk rk m u1 v1 ... um vm:令前 个片段生成字符串 ,后 个片段生成字符串 。询问 中有多少个字符串同时以 开头、以 结尾。
多重集中的相同字符串按实例分别计数;删除一个实例不会删除其他相同内容的实例。查询的前缀和后缀可以重叠,例如某个字符串可以同时是自己的前缀和后缀。
输入格式
第一行两个整数 ,满足 。
第二行是长度为 的字符串 ,只包含小写英文字母。
接下来 行,第 行给出第 个操作,格式如上。所有片段均满足 ,各生成字符串的片段数都是正整数。删除操作的 指输入中的操作编号,而不是第几次插入。
保证以下三项之和不超过 :所有插入操作的片段数、所有查询前缀的片段数、所有查询后缀的片段数。
每个输入文件只有一组数据。
输出格式
对每个 ? 操作输出一行一个整数,表示满足条件的字符串实例数量。
样例
输入:
8 7
abcaabbc
+ 3 1 3 2 4 3 8
+ 2 1 4 1 8
+ 1 2 4
? 1 5 6 1 7 8
- 3
+ 1 2 5
? 1 2 3 1 5 5
输出:
2
1