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.


44% Solution Ratio
NirjhorEarliest, Jun '21
nusuBotFastest, 0.2s
ValeraGrinenkoLightest, 27 MB
serotoninShortest, 1461B
Toph uses cookies. By continuing you agree to our Cookie Policy.