P4465 [CTT] JZPSTR

You need to perform three types of operations on a string: 0. Insert a string $y_i$ at position $x_i$. 1. Delete the substring in the interval $[x_i, y_i)$. 2. Query how many times a given substring $z_i$ occurs in the substring of the interval $[x_i, y_i)$. The indices of the string start from $0$ (that is, the first character has index $0$). Initially, the string is empty. For the insertion operation, after insertion the first character of $y_i$ should have index $x_i$. For the deletion operation, the interval $[x_i, y_i)$ is a left-closed, right-open interval. For the query operation, the interval $[x_i, y_i)$ is a left-closed, right-open interval. All inserted strings and query strings are non-empty and contain only characters $\texttt{0}\sim\texttt{9}$. All query intervals and deletion intervals are non-empty. The input is guaranteed to be valid. If you do not understand the term "left-closed, right-open interval", please see the sample explanation.

The first line contains an integer $T$, the number of operations. In the following $T$ lines, the first number $p_i$ indicates the type of the operation: - If $p_i=0$, then an integer $x_i$ and a string $y_i$ follow, indicating an insertion. - If $p_i=1$, then two integers $x_i$ and $y_i$ follow, indicating a deletion. - If $p_i=2$, then two integers $x_i$ and $y_i$, and a string $z_i$ follow, indicating a query.

For each query operation, output one line with the answer to that query.

Sample explanation: - After the first operation, the string is $\texttt{894894894}$. - In the second operation, the queried interval is $\texttt{89}$, which contains no $\texttt{894}$. - In the third operation, the queried interval is $\texttt{894894894}$, which contains three $\texttt{894}$. - After the fourth operation, the string is $\texttt{8964894894}$. - In the fifth operation, the queried interval is $\texttt{896489489}$, which contains one $\texttt{64}$. - In the sixth operation, the queried interval is $\texttt{896489489}$, which contains one $\texttt{894}$. - After the seventh operation, the string is $\texttt{894894}$. - In the eighth operation, the queried interval is $\texttt{894894}$, which contains two $\texttt{894}$. Constraints: - In $50\%$ of the testdata, the number of queries $\le 100$ (not the number of operations). - In $100\%$ of the testdata, the total inserted length $\le 2\times 10^6$, the string length at any time $\le 10^6$, the number of insertions $\le 1001$, the number of deletions $\le 1000$, and the total length of all queried $z_i$ $\le 10^4$. Source: 2012 CTT internal contest, by gyz. Translated by ChatGPT 5