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.