Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Initially you have an empty list $D$. In this problem you will be asked to execute three types of queries. The query types are described below.

$1$ $S$

In this query, you have to add string $S$ to the list $D$$2$ $T$ $L$

In this query you have to remove the suffix of length $L$ from the $T^{th}$ added string$3$ $i$ $j$

Let,

$min(D_{i},D_{j})$ = Lexicographically smallest among $D_{i}$and $D_{j}$

$max(D_{i}, D{j})$= Lexicographically largest among $D_{i}$and $D_{j}$

In this query you have to count the number of strings $D_{k}$ such that $min(D_{i},D_{j}) \leq D_{k} \leq max(D_{i},D_{j})$ and $1\leq k \leq |D|$. Note that, we compare strings lexicographically. Lexicographical order means dictionary order.

To know more about lexicographical order, visit https://en.wikipedia.org/wiki/Lexicographic_order*All the strings will contain lowercase english alphabets only.*

The first line of the input will contain a single integer $Q$. Each of the next $Q$ lines will contain one of the three types of queries as below.

$1$ $S$

Add $S$ to your list.$2$ $T$ $L$

Here, $1\leq T\leq |D|$ and $1 \leq L \leq |D_{T}|$$3$ $i$ $j$

Here, $1 \leq i,j \leq |D|$

Note that, there will be at least one query of type $1$ and one query of type $3$.

$\textbf{Constraints:}$

For **Subtask #1 (10 points):**

$1 \leq Q \leq 300$

$1 \leq |S| \leq 10$

$1 \leq \sum(|D_{i}|) \leq 100$

There will be no query of type 2.

For **Subtask #2 (90 points):**

$1 \leq Q \leq 10^{6}$

$1 \leq |S| \leq 10^{5}$

$1 \leq \sum(|D_{i}|) \leq 10^{6}$

For query type $3$, print the number of such strings in a single line.

Input | Output |
---|---|

5 1 aa 1 aaa 1 aaaa 2 2 2 3 1 3 | 2 |

Input | Output |
---|---|

8 1 abc 1 defg 3 1 2 1 hijkl 3 2 3 2 2 1 2 2 3 3 2 3 | 2 2 3 |

After executing the $7^{th}$query, the list is $D$ $=$ [ “abc“, ““,”hijkl” ]. So, the answer to the $8^{th}$query is $3$. |

42% Solution Ratio

NirjhorEarliest,

Deshi_TouristFastest, 0.2s

ValeraGrinenkoLightest, 27 MB

serotoninShortest, 1461B

Login to submit

The solution to this problem requires Trie and Binary Indexed Tree/Segment tree. Steps are given bel...