PROBLEM LINK:Author: Sergey Kulik DIFFICULTY:Mediumhard PREREQUISITES:String hashing, range tree queries PROBLEM:There are $N$ initially empty towers of letters. There are also $M$ favorite words. There are three types of queries:
You need to process $Q$ queries. QUICK EXPLANATION:We can compare whether two strings are equal by comparing their hashes. For this problem, we can use polynomial hashing so we can compute the hash of any substring easily. There are only $O(\sqrt{S})$ distinct lengths in the favorite words, where $S$ is the sum of the lengths of the favorite words. So during a type $0$ query, we can compute $O(\sqrt{S})$ hashes of suffixes, one for each distinct length. Before processing any type $1$ or $2$ query, process all type $0$ queries beforehand so that you know where each favorite word will appear in the future. Then we process the queries for each favorite word separately. Specifically, when processing the $P$th favorite word:
For a fixed $P$, each of these constitutes a range sum with point updates, so a Fenwick tree can answer them quickly. For an asymptotically faster solution, use sqrt decomposition instead of a Fenwick tree. EXPLANATION:Coming soon. Time Complexity:$O(N + Q (\sqrt{N} + \sqrt{S}))$ where $S$ is the sum of the lengths of the favorite words. AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 19 Jun '16, 15:18

There are only O(S−−√)O(S) distinct lengths in the favorite words, where SS is the sum of the lengths of the favorite words.  Can some one explain the meaning of this line and also how this inference is made? answered 13 Dec '17, 19:30

Seems that there is a faster solution, both theoretically and practically. Submission: https://www.codechef.com/viewsolution/20850365 (Second fastest submission among all accepted ones) Assume that any of favourite strings is not another one's prefix, and we can see that the total number of occurences is less than sigmaWi. So for each favourite string we maintain a dynamic segment tree storing its occurrence, and we are done. When our assumption is wrong, we first reverse the favourite strings, then build an ACAutomata and get the tree formed by its fail links. Easy to see that, if a node represent string S, its ancestors represent suffixes of S. Then, when we attach a char to the end of some string, we find the maximal favourite suffix of the resulting string, get its corresponding node, and add counting variables in its ancestors by one. This can be done by maintain a segment tree of euler tour order. However, as there are more than one tower, the problem is actually 2D. So we can use Divide and Conquer + Fenwick Tree to solve it, in the same way as problem <mokia> in some year's BOI. Total complexity: Qlog(Q)log(W) answered 15 Oct '18, 19:16
