8768: BZOJ4768:2555加强版之wxh loves substring
Memory Limit:512 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
wxh太强了,他觉得你们太菜了,所以懒得写背景了,给你一个字符串init,要求你支持三个操作 (1):在当前字符串的后面插入若干个字符 (2):在当前字符串的后面删除若干个字符 (3):询问字符串s在当前字符串中出现了几次?(作为连续子串) 你必须在线支持这些操作。
输入格式
第一行一个数Q表示操作个数 第二行一个字符串表示初始字符串init 接下来Q行,每行2个字符串Type,Str Type是ADD的话表示在后面插入。 Type是DEL的话表示在后面删除。 Type是QUERY的话表示询问某字符串在当前字符串中出现了几次。 为了体现在线操作,你需要维护一个变量mask,初始值为0 读入串Str之后,使用这个过程将之解码成真正询问的串TrueStr。 询问的时候,对TrueStr询问后输出一行答案Result 然后mask = mask xor Result 插入的时候,将TrueStr插到当前字符串后面即可。 HINT:ADD和QUERY操作的字符串都需要解压 字符集大写字母 数据字符串变化长度以及初始长度和 <= 600000,询问次数 <= 10000,询问总长度 <= 3000000
输出格式
样例输入
3 A QUERY B ADD BBABBBBAAB DEL 1
样例输出
0
提示
应出题人要求放出数据如下:http://www.lydsy.com/JudgeOnline/upload/wxh.zip
题目来源
By nzhtl1477