### PROBLEM LINK:

**Author:** Sergey Kulik

**Testers:** Vasya Antoniuk and Kevin Atienza

**Translators:** Vasya Antoniuk (Russian), Sergey Kulik (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)

**Editorialist:** Kevin Atienza

### DIFFICULTY:

Medium-hard

### 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:

- 0 X C: put the letter C to the top of the X th tower.
- 1 L R P: find the number of towers in the range [L, R] which contain the P th favorite word.
- 2 L R P: find the number of occurrences of the P th favorite word across all towers in the range [L, R].

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:

- Consider only type 1 and 2 queries with this P, and
- Consider only type 0 queries that yield a new occurrence of 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.