Description

 阿狸喜欢收藏各种稀奇古怪的东西,最近他淘到一台老式的打字机。打字机上只有28个按键,分别印有26个小写英文字母和’B’、’P’两个字母。

经阿狸研究发现,这个打字机是这样工作的:

l 输入小写字母,打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。

l 按一下印有’B’的按键,打字机凹槽中最后一个字母会消失。

l 按一下印有’P’的按键,打字机会在纸上打印出凹槽中现有的所有字母并换行,但凹槽中的字母不会消失。

例如,阿狸输入aPaPBbP,纸上被打印的字符如下:

a

aa

ab

我们把纸上打印出来的字符串从1开始顺序编号,一直到n。打字机有一个非常有趣的功能,在打字机中暗藏一个带数字的小键盘,在小键盘上输入两个数(x,y)(其中1≤x,y≤n),打字机会显示第x个打印的字符串在第y个打印的字符串中出现了多少次。

阿狸发现了这个功能以后很兴奋,他想写个程序完成同样的功能,你能帮助他么?

Input

 输入的第一行包含一个字符串,按阿狸的输入顺序给出所有阿狸输入的字符。

第二行包含一个整数m,表示询问个数。

接下来m行描述所有由小键盘输入的询问。其中第i行包含两个整数x, y,表示第i个询问为(x, y)。

Output

 输出m行,其中第i行包含一个整数,表示第i个询问的答案。

Sample Input

aPaPBbP

3

1 2

1 3

2 3

Sample Output

2

1

0

HINT

 1<=N<=10^5

1<=M<=10^5
输入总长<=10^5
逗号表达式竟然又一次出锅?why以前用的好好的 今天垃圾蒟蒻我调试半天
考虑m*l做法怎么做 很显然就是把所有的串建在一棵trie上 然后针对每个串我去跑一遍在那个串上有多少个是符合条件的
那么如果字符串A可以有fail指向B那么显然 B将会是A的一个后缀  那么可以知道我A包含了B  那么 假如A串中有n个fail指向了B 那么显然 B就在A 中出现了n次 直接按照这个思路做 复杂度仍然太高怎么办 考虑将我们的fail边反向 那么显然因为fail只有一个父节点 那么我这个反向的边建出来的一定是一棵树  那么我们将会获得一个离线的做法 怎么办首先将所有的询问离线进来 按照询问的y从小到大排序 那么我将整个操作序列也离线进来 然后每次移动的时候如果串的个数增加了且恰好等于我当前询问的y 那么我会把询问这个y的x全部都做一遍 具体怎么做考虑用树状数组维护dfs序  我首先标出dfs序列 然后每次做的时候把当前节点的都+1表示我这个如果询问我的子树我可以快速ologn的得到答案 如果遇到了P 那么就打印,然后加一个字符串 如果遇到了B 就删除 然后跳到trie树上的fa 继续
注意:对于每个x串,只有能通过fail指针指向它的末尾节点的y串节点才能计数 统计的话因为是fail建树直接统计子树是没问题的

 


elijahqi

退役了 现在在商院 偶尔打CF,有时有ACM regional也去玩一下

发表评论