P5212 SubString

Given a string `init`, you need to support two operations: - Append a string to the end of the current string. - Query how many times a string $s$ appears in the current string (as a contiguous substring). The operations are strictly online.

The first line contains an integer $Q$, the number of operations. The second line contains a string, the initial string `init`. Next come $Q$ lines. Each line contains two strings, `Type` and `Str`. - `Type` is `ADD`, meaning to append a string to the end. - `Type` is `QUERY`, meaning to ask how many times a string appears in the current string. To enforce online processing, you need to maintain a variable `mask`, initially $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); } ``` After reading `Str`, use this process to decode it into the real string `TrueStr`. For a query, query `TrueStr` and output one line with the answer `Result`. Then update $mask = mask \bigoplus Result$. For an insertion, append `TrueStr` to the end of the current string. **Note: the strings in both `ADD` and `QUERY` operations must be decoded.**

For each `QUERY` operation, output how many times the queried string appears in the current string.

$|\mathrm{init}| \leq 6 \times 10^5$, $Q \leq 6 \times 10^5$, and the total length of all queried strings is at most $3 \times 10^6$. It is guaranteed that the strings contain only `A` and `B`. To avoid slow judging, for test points $2,3,5,6,8,11$ the time limit is 3 s, and for the others it is 1 s. Original problem: BZOJ 2555. Translated by ChatGPT 5