P8451 [LSOT-1] Crosspain


Let $S_0=\varnothing$. Maintain a data structure that supports the following operations: - `1 hoc s`: Let $S_i=S_{hoc}\cup\{s\}$, where $s$ is a string (it is guaranteed that before the operation $s\notin S_{hoc}$). - `2 hoc s`: Let $S_i=S_{hoc}$, and query the sum of the number of occurrences of all strings in $S_i$ within the given string $s$.

The first line contains a positive integer $q$, indicating the number of queries. The next $q$ lines each contain one operation, in the format described above.

For each operation 2, output one line containing the answer.

### Sample Explanation In the third line, we ask how many times the strings in version $0$ appear in `abc`. Since version $0$ is empty, it appears $0$ times. In the fifth line, we ask how many times the strings in version $3$ appear in `defg`. Since version $3$ contains the string `def`, it appears $1$ time. In the sixth line, we ask how many times the strings in version $1$ appear in `abcd`. Since version $1$ contains the string `abc`, it appears $1$ time. ### Constraints and Notes **"This problem uses bundled testdata."** - $\texttt{Subtask 1(10 pts):} \displaystyle \sum|s_i|\le 1000$. - $\texttt{Subtask 2(20 pts):}$ All added strings have the same length. - $\texttt{Subtask 3(20 pts):}$ All added strings contain only one kind of character. - $\texttt{Subtask 4(20 pts):}q\le 10^3$. - $\texttt{Subtask 5(30 pts):}$ No special restrictions. For all testdata, $1\le q\le 5\times 10^5$, $\displaystyle 1\le \sum_i|s_i|\le 10^6$. All strings contain only lowercase letters. Translated by ChatGPT 5