P6164 [Template] Suffix Balanced Tree

The correctness of the name "Suffix Balanced Tree" is questionable, because the definition of "Weight Balanced Tree" given by clj is ambiguous. I am also not good at strings, so I did not verify it either.

You are given a string `init`. You need to support three operations: 1. Insert several characters at the end of the current string. 2. Delete several characters from the end of the current string. 3. Ask how many times a string $s$ appears in the current string (as a consecutive substring). You must support these operations online.

The first line contains an integer $q$, the number of operations. The second line contains a string, the initial string `init`. Then follow $q$ lines, each containing two strings `Type Str`. If `Type` is `ADD`, it means inserting at the end. If `Type` is `DEL`, it means deleting from the end. If `Type` is `QUERY`, it means asking how many times a certain string appears in the current string. To reflect online operations, you need to maintain a variable `mask`, whose initial value is $0$. After reading the string `Str`, use the following process to decode it into the real queried string `TrueStr`. When querying, query `TrueStr` and output one line with the answer `Result`. Then update `mask = mask xor Result`. When inserting, just append `TrueStr` to the end of the current string. 

For each operation of type $3$, output one line with an integer representing the answer.

Constraints: the total length of the string changes and the initial length satisfy $\le 8 \times 10^5$. The number of queries is $\le 10^5$. The total length of all query strings is $\le 3 \times 10^6$. The character set is uppercase letters. Note that the strings in `ADD` and `QUERY` operations both need to be decompressed. Translated by ChatGPT 5