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

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

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

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

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

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,

nusuBotFastest, 0.2s

ValeraGrinenkoLightest, 27 MB

serotoninShortest, 1461B

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