Practice on Toph

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

List of Strings

By Hasinur_ · Limits 1s, 512 MB

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

  • 11 SS
    In this query, you have to add string SS to the list DD

  • 22 TT LL
    In this query you have to remove the suffix of length LL from the TthT^{th} added string

  • 33 ii jj
    min(Di,Dj)min(D_{i},D_{j}) = Lexicographically smallest among DiD_{i}and DjD_{j}
    max(Di,Dj)max(D_{i}, D{j})= Lexicographically largest among DiD_{i}and DjD_{j}

    In this query you have to count the number of strings DkD_{k} such that min(Di,Dj)Dkmax(Di,Dj)min(D_{i},D_{j}) \leq D_{k} \leq max(D_{i},D_{j}) and 1kD1\leq k \leq |D|. Note that, we compare strings lexicographically. Lexicographical order means dictionary order.
    To know more about lexicographical order, visit

    All the strings will contain lowercase english alphabets only.


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

  • 11 SS
    Add SS to your list.

  • 22 TT LL
    Here, 1TD1\leq T\leq |D| and 1LDT1 \leq L \leq |D_{T}|

  • 33 ii jj
    Here, 1i,jD1 \leq i,j \leq |D|

    Note that, there will be at least one query of type 11 and one query of type 33.


For Subtask #1 (10 points):

  • 1Q3001 \leq Q \leq 300

  • 1S101 \leq |S| \leq 10

  • 1(Di)1001 \leq \sum(|D_{i}|) \leq 100

  • There will be no query of type 2.

For Subtask #2 (90 points):

  • 1Q1061 \leq Q \leq 10^{6}

  • 1S1051 \leq |S| \leq 10^{5}

  • 1(Di)1061 \leq \sum(|D_{i}|) \leq 10^{6}


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


1 aa
1 aaa
1 aaaa
2 2 2
3 1 3
1 abc
1 defg
3 1 2
1 hijkl
3 2 3
2 2 1
2 2 3
3 2 3

After executing the 7th7^{th}query, the list is DD == [ “abc“, ““,”hijkl” ]. So, the answer to the 8th8^{th}query is 33.



    44% Solution Ratio

    NirjhorEarliest, 4M ago

    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...

    Toph uses cookies. By continuing you agree to our Cookie Policy.