bzoj#P4768. 2555 加强版之 wxh loves substring

2555 加强版之 wxh loves substring

题目描述

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

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

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

输入格式

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

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

提示:ADDQUERY 操作的字符串都需要解压。

输出格式

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