This problem can be solved with $Heavy-Light$ trick.

  1. Split the input strings (Chander Buri's strings) in Heavy and Light groups.

  2. Build a Trie.

  3. Put the Light group in the trie.

  4. Put the prefix which is the largest among the light prefixes of each string of Heavy group in trie.

  5. Now execute the queries.

  6. If an update operation occurs then change the character of the string and update only the light largest prefix in the trie.

  7. If an ask operation occurs then two scenario may appear. If the prefix $T$ is light then search it in the trie. If the prefix $T$ is heavy then search it in the Heavy group.

Note: Maintain the trie in a way such that you don't get MLE. How? Recycle the unused trie nodes.

Time complexity: $O(N\sqrt N)$

Memory complexity: $O(N)$

Contributors

Statistics

64% Solution Ratio
mh755628Earliest, Jan '21
mumith_fahim99Fastest, 0.1s
BrehamPieLightest, 13 MB
mh755628Shortest, 1958B
Toph uses cookies. By continuing you agree to our Cookie Policy.