F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:本站提供各级各类比赛备战资源(Noip提高组及以下),有意者请联系Lydsy2012@163.com,仅限教师及家长用户。
Problem 4768. -- 2555加强版之wxh loves substring

4768: 2555加强版之wxh loves substring

Time Limit: 20 Sec  Memory Limit: 512 MB
Submit: 278  Solved: 76
[Submit][Status][Discuss]

Description

wxh太强了,他觉得你们太菜了,所以懒得写背景了,给你一个字符串init,要求你支持三个操作
(1):在当前字符串的后面插入若干个字符
(2):在当前字符串的后面删除若干个字符
(3):询问字符串s在当前字符串中出现了几次?(作为连续子串)
你必须在线支持这些操作。

Input

第一行一个数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操作的字符串都需要解压
字符集大写字母
数据字符串变化长度以及初始长度和 <= 800000,询问次数 <= 100000,询问总长度 <= 3000000

Output

Sample Input

3
A
QUERY B
ADD BBABBBBAAB
DEL 1

Sample Output

0

HINT

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


Source

By nzhtl1477

[Submit][Status][Discuss]

HOME Back