Editorial for List of Strings

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

  1. Take all the input queries and save them. You need to answer the queries offline here.

  2. Insert all the strings in a trie, mark the endnodes and track frequency for each node.

  3. Run a DFS on the trie and determine dfs time for each node in a way that lexicographically smaller prefix get smaller dfs time.

  4. Build a BIT for cumulative sum, add the values of each trie nodes frequency to it.

  5. Start executing the type 2 and 3 queries.
    if a type 2 query comes then change the strings endnode by going up of the trie. Change data accordingly in BIT.
    If a type 3 query comes then determine the dfs time of endnodes of the given two strings. Get the sum between this two endnodes’ dfs time and print it.

    Statistics


    44% Solution Ratio

    NirjhorEarliest, 3M ago

    Deshi_TouristFastest, 0.2s

    ValeraGrinenkoLightest, 27 MB

    serotoninShortest, 1461B

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