Initially you have an empty list . In this problem you will be asked to execute three types of queries. The query types are described below.
In this query, you have to add string to the list
In this query you have to remove the suffix of length from the added string
= Lexicographically smallest among and
= Lexicographically largest among and
In this query you have to count the number of strings such that and . 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 . Each of the next lines will contain one of the three types of queries as below.
Add to your list.
Note that, there will be at least one query of type and one query of type .
For Subtask #1 (10 points):
There will be no query of type 2.
For Subtask #2 (90 points):
For query type , print the number of such strings in a single line.
5 1 aa 1 aaa 1 aaaa 2 2 2 3 1 3
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 query, the list is [ “abc“, ““,”hijkl” ]. So, the answer to the query is .
Login to submit
The solution to this problem requires Trie and Binary Indexed Tree/Segment tree. Steps are given bel...