#P4768. 2555加强版之wxh loves substring

2555加强版之wxh loves substring

题目描述

wxh 太强了,他觉得你们太菜了,所以懒得写背景了,给你一个字符串 initinit,要求你支持三个操作。

  1. 在当前字符串的后面插入若干个字符;
  2. 在当前字符串的后面删除若干个字符;
  3. 询问字符串 ss 在当前字符串中出现了几次?(作为连续子串)。

你必须在线支持这些操作。

输入格式

第一行一个数 QQ 表示操作个数。 第二行一个字符串表示初始字符串 initinit。 接下来 QQ 行,每行 22 个字符串 Type,StrType,Str。 TypeType 是 ADD 的话表示在后面插入。 TypeType 是 DEL 的话表示在后面删除。 TypeType 是 QUERY 的话表示询问某字符串在当前字符串中出现了几次。

为了体现在线操作,你需要维护一个变量 maskmask,初始值为 00。 读入串 StrStr 之后,使用这个过程将之解码成真正询问的串 TrueStrTrueStr。 询问的时候,对 TrueStrTrueStr 询问后输出一行答案 ResultResult。 然后 mask=maskxor⁡Resultmask = mask \operatorname{xor} Result。 插入的时候,将 TrueStrTrueStr 插到当前字符串后面即可。

提示:ADD 和 QUERY 操作的字符串都需要解压。

输出格式

无

3
A
QUERY B
ADD BBABBBBAAB
DEL 1
0

数据规模与约定

对于 100%100\% 的数据,字符集大写字母。 数据字符串变化长度以及初始长度和 ≤6×105\le 6\times 10^5,询问次数 ≤104\le 10^4,询问总长度 ≤3×106\le 3\times 10^6。

提示

应出题人要求放出数据如下:http://www.lydsy.com/JudgeOnline/upload/wxh.zip。

题目来源

By nzhtl1477