SubString
题目描述
给定一个字符串 `init`，要求支持两个操作：
- 在当前字符串的后面插入一个字符串。
- 询问字符串 $s$ 在当前字符串中出现了几次。(作为连续子串)
强制在线。
输入输出格式
输入格式
第一行一个整数 $Q$ 表示操作个数。
第二行一个字符串表示初始字符串 `init`。
接下来 $Q$ 行，每行 $2$ 个字符串 `Type`,`Str`。
- `Type` 是 `ADD`，表示在后面插入字符串。
- `Type` 是 `QUERY`，表示询问某字符串在当前字符串中出现了几次。
为了体现在线操作，你需要维护一个变量 `mask`，初始值为 $0$。
```cpp
String decodeWithMask(String s, int mask) {
char[] chars = s.toCharArray();
for (int j = 0; j < chars.length; j++) {
mask = (mask * 131 + j) % chars.length;
char t = chars[j];
chars[j] = chars[mask];
chars[mask] = t;
}
return new String(chars);
}
```
读入串 `Str` 之后，使用这个过程将之解码成真正询问的串 `TrueStr`。
询问的时候，对 `TrueStr` 询问后输出一行答案 `Result`。
然后 $mask=mask \bigoplus Result$。
插入的时候，将`TrueStr`插到当前字符串后面即可。
**注意：`ADD` 和 `QUERY` 操作的字符串都需要解压。**
输出格式
对于每一个 `QUERY` 操作，输出询问的字符串在当前字符串中出现了几次。
输入输出样例
输入样例 #1
2
A
QUERY B
ADD BBABBBBAAB输出样例 #1
0说明
$|\mathrm{init}| \leq 6 \times 10^5$，$Q \leq 6\times 10^5$，询问总长度 $\leq 3 \times 10^6$。
保证字符串中只会出现 `A` 和 `B`。
为防止评测过慢，对于测试点 $2,3,5,6,8,11$ 时限为 3s，其余为 1s。
原题：BZOJ 2555