首页 > 题解 > bzoj 2555 SubString

bzoj 2555 SubString

Description

懒得写背景了,给你一个字符串init,要求你支持两个操作

(1):在当前字符串的后面插入一个字符串

(2):询问字符串s在当前字符串中出现了几次?(作为连续子串)

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

Input

第一行一个数Q表示操作个数

第二行一个字符串表示初始字符串init

接下来Q行,每行2个字符串Type,Str

Type是ADD的话表示在后面插入字符串。

Type是QUERY的话表示询问某字符串在当前字符串中出现了几次。

为了体现在线操作,你需要维护一个变量mask,初始值为0

读入串Str之后,使用这个过程将之解码成真正询问的串TrueStr。

询问的时候,对TrueStr询问后输出一行答案Result

然后mask = mask xor Result

插入的时候,将TrueStr插到当前字符串后面即可。

HINT:ADD和QUERY操作的字符串都需要解压

Output

Sample Input

2
A
QUERY B
ADD BBABBBBAAB

Sample Output

0

HINT

40 % 的数据字符串最终长度 <= 20000,询问次数<= 1000,询问总长度<=10000

100 % 的数据字符串最终长度 <= 600000,询问次数<= 10000,询问总长度<=3000000

新加数据一组--2015.05.20

题解

加入新节点后,它的祖先的right集合都要加1

因为加入节点的时候Parent树的形态会改变,那就再套个数据结构。。动态树肯定是LCT比较好。。

但是网上说暴力比LCT快4倍= =

还有就是我调了一下午是因为读入的decode写错了。。。。注意mask用的时候不能直接用,要提出来个值。。


2 COMMENTS

  1. Idvz2018-02-07 下午7:32

    讲道理,我觉得这个insert有问题的啊,应该是if(dis[ch[pre][x]] == dis[pre] + 1)

如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×