Fedya the Potter Strikes Back
Contest: Codeforces Round 612 (Div. 1)
Difficulty rating: 3200
Tags: data structures, strings

Fedya has a string $$$S$$$, initially empty, and an array $$$W$$$, also initially empty.

There are $$$n$$$ queries to process, one at a time. Query $$$i$$$ consists of a lowercase English letter $$$c_i$$$ and a nonnegative integer $$$w_i$$$. First, $$$c_i$$$ must be appended to $$$S$$$, and $$$w_i$$$ must be appended to $$$W$$$. The answer to the query is the sum of suspiciousnesses for all subsegments of $$$W$$$ $$$[L, \ R]$$$, $$$(1 \leq L \leq R \leq i)$$$.

We define the suspiciousness of a subsegment as follows: if the substring of $$$S$$$ corresponding to this subsegment (that is, a string of consecutive characters from $$$L$$$-th to $$$R$$$-th, inclusive) matches the prefix of $$$S$$$ of the same length (that is, a substring corresponding to the subsegment $$$[1, \ R - L + 1]$$$), then its suspiciousness is equal to the minimum in the array $$$W$$$ on the $$$[L, \ R]$$$ subsegment. Otherwise, in case the substring does not match the corresponding prefix, the suspiciousness is $$$0$$$.

Help Fedya answer all the queries before the orderlies come for him!

Input format:
The first line contains an integer $$$n$$$ $$$(1 \leq n \leq 600\,000)$$$ — the number of queries.

The $$$i$$$-th of the following $$$n$$$ lines contains the query $$$i$$$: a lowercase letter of the Latin alphabet $$$c_i$$$ and an integer $$$w_i$$$ $$$(0 \leq w_i \leq 2^{30} - 1)$$$.

All queries are given in an encrypted form. Let $$$ans$$$ be the answer to the previous query (for the first query we set this value equal to $$$0$$$). Then, in order to get the real query, you need to do the following: perform a cyclic shift of $$$c_i$$$ in the alphabet forward by $$$ans$$$, and set $$$w_i$$$ equal to $$$w_i \oplus (ans \ \& \ MASK)$$$, where $$$\oplus$$$ is the bitwise exclusive "or", $$$\&$$$ is the bitwise "and", and $$$MASK = 2^{30} - 1$$$.

Output format:
Print $$$n$$$ lines, $$$i$$$-th line should contain a single integer — the answer to the $$$i$$$-th query.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
For convenience, we will call "suspicious" those subsegments for which the corresponding lines are prefixes of $$$S$$$, that is, those whose suspiciousness may not be zero.

As a result of decryption in the first example, after all requests, the string $$$S$$$ is equal to "abacaba", and all $$$w_i = 1$$$, that is, the suspiciousness of all suspicious sub-segments is simply equal to $$$1$$$. Let's see how the answer is obtained after each request:

1. $$$S$$$ = "a", the array $$$W$$$ has a single subsegment — $$$[1, \ 1]$$$, and the corresponding substring is "a", that is, the entire string $$$S$$$, thus it is a prefix of $$$S$$$, and the suspiciousness of the subsegment is $$$1$$$.

2. $$$S$$$ = "ab", suspicious subsegments: $$$[1, \ 1]$$$ and $$$[1, \ 2]$$$, total $$$2$$$.

3. $$$S$$$ = "aba", suspicious subsegments: $$$[1, \ 1]$$$, $$$[1, \ 2]$$$, $$$[1, \ 3]$$$ and $$$[3, \ 3]$$$, total $$$4$$$.

4. $$$S$$$ = "abac", suspicious subsegments: $$$[1, \ 1]$$$, $$$[1, \ 2]$$$, $$$[1, \ 3]$$$, $$$[1, \ 4]$$$ and $$$[3, \ 3]$$$, total $$$5$$$.

5. $$$S$$$ = "abaca", suspicious subsegments: $$$[1, \ 1]$$$, $$$[1, \ 2]$$$, $$$[1, \ 3]$$$, $$$[1, \ 4]$$$ , $$$[1, \ 5]$$$, $$$[3, \ 3]$$$ and $$$[5, \ 5]$$$, total $$$7$$$.

6. $$$S$$$ = "abacab", suspicious subsegments: $$$[1, \ 1]$$$, $$$[1, \ 2]$$$, $$$[1, \ 3]$$$, $$$[1, \ 4]$$$ , $$$[1, \ 5]$$$, $$$[1, \ 6]$$$, $$$[3, \ 3]$$$, $$$[5, \ 5]$$$ and $$$[5, \ 6]$$$, total $$$9$$$.

7. $$$S$$$ = "abacaba", suspicious subsegments: $$$[1, \ 1]$$$, $$$[1, \ 2]$$$, $$$[1, \ 3]$$$, $$$[1, \ 4]$$$ , $$$[1, \ 5]$$$, $$$[1, \ 6]$$$, $$$[1, \ 7]$$$, $$$[3, \ 3]$$$, $$$[5, \ 5]$$$, $$$[5, \ 6]$$$, $$$[5, \ 7]$$$ and $$$[7, \ 7]$$$, total $$$12$$$.

In the second example, after all requests $$$S$$$ = "aaba", $$$W = [2, 0, 2, 0]$$$.

1. $$$S$$$ = "a", suspicious subsegments: $$$[1, \ 1]$$$ (suspiciousness $$$2$$$), totaling $$$2$$$.

2. $$$S$$$ = "aa", suspicious subsegments: $$$[1, \ 1]$$$ ($$$2$$$), $$$[1, \ 2]$$$ ($$$0$$$), $$$[2, \ 2]$$$ ( $$$0$$$), totaling $$$2$$$.

3. $$$S$$$ = "aab", suspicious subsegments: $$$[1, \ 1]$$$ ($$$2$$$), $$$[1, \ 2]$$$ ($$$0$$$), $$$[1, \ 3]$$$ ( $$$0$$$), $$$[2, \ 2]$$$ ($$$0$$$), totaling $$$2$$$.

4. $$$S$$$ = "aaba", suspicious subsegments: $$$[1, \ 1]$$$ ($$$2$$$), $$$[1, \ 2]$$$ ($$$0$$$), $$$[1, \ 3]$$$ ( $$$0$$$), $$$[1, \ 4]$$$ ($$$0$$$), $$$[2, \ 2]$$$ ($$$0$$$), $$$[4, \ 4]$$$ ($$$0$$$), totaling $$$2$$$.

In the third example, from the condition after all requests $$$S$$$ = "abcde", $$$W = [7, 2, 10, 1, 7]$$$.

1. $$$S$$$ = "a", suspicious subsegments: $$$[1, \ 1]$$$ ($$$7$$$), totaling $$$7$$$.

2. $$$S$$$ = "ab", suspicious subsegments: $$$[1, \ 1]$$$ ($$$7$$$), $$$[1, \ 2]$$$ ($$$2$$$), totaling $$$9$$$.

3. $$$S$$$ = "abc", suspicious subsegments: $$$[1, \ 1]$$$ ($$$7$$$), $$$[1, \ 2]$$$ ($$$2$$$), $$$[1, \ 3]$$$ ( $$$2$$$), totaling $$$11$$$.

4. $$$S$$$ = "abcd", suspicious subsegments: $$$[1, \ 1]$$$ ($$$7$$$), $$$[1, \ 2]$$$ ($$$2$$$), $$$[1, \ 3]$$$ ( $$$2$$$), $$$[1, \ 4]$$$ ($$$1$$$), totaling $$$12$$$.

5. $$$S$$$ = "abcde", suspicious subsegments: $$$[1, \ 1]$$$ ($$$7$$$), $$$[1, \ 2]$$$ ($$$2$$$), $$$[1, \ 3]$$$ ( $$$2$$$), $$$[1, \ 4]$$$ ($$$1$$$), $$$[1, \ 5]$$$ ($$$1$$$), totaling $$$13$$$.

Example input:
7
a 1
a 0
y 3
y 5
v 4
u 6
r 8

Example output:
1
2
4
5
7
9
12

Example input:
4
a 2
y 2
z 0
y 2

Example output:
2
2
2
2

Editorial:
Let $$$ans_{i}$$$ be the answer for the moment after $$$i$$$ queries. Then, $$$s_{i} = ans_{i} - ans_{i-1}$$$ is equal to the sum of suspiciousness of suffixes of the string after $$$i$$$ queries. If we calculate $$$s_{i}$$$, $$$ans$$$ will be the prefix sums of this array.
Let's maintain the KMP tree of the string. Each vertex of the tree corresponds to a prefix of the string. Let $$$S$$$ be the subset of suffixes, which are equal to the corresponding prefixes. We can note that $$$S$$$ is exactly the path from the root to the current vertex in the tree.
Let $$$s_{v}$$$ be the next character of vertex of KMP, which corresponds to the prefix with length $$$v$$$ (the string is indexed from $$$0$$$). Let's find out what happens after adding a new character to the end of the string. Some suffixes from $$$S$$$ can't be extended with this character (keeping the condition about equality to the prefix), so they will be removed from the set. Also, if the new character is equal to $$$s_{0}$$$, a suffix with length $$$1$$$ will be added to the set. These are the only modifications that will be applied to $$$S$$$.
We want to find all elements of $$$S$$$, which will be removed after a certain query. Let's denote the number of these elements by $$$r$$$. If we find them in $$$O(r)$$$, the amortized time will be $$$O(n)$$$. A suffix can't be extended if and only if the next character of its vertex is not equal to the new character. We need to find all these vertexes on the way up from the last vertex. Let $$$link_{v}$$$ be the closest ancestor of $$$v$$$ with the different next character (we can calculate it for each vertex when it is added). Let's ascend from vertex $$$v$$$. If we are in a vertex with the same next character as in the vertex $$$v$$$, then we will go to the $$$link_{v}$$$, otherwise, we will handle this vertex as a removing suffix and go to the parent vertex. It's clear that it works in $$$O(r)$$$.
Now our task is just adding a suffix with length $$$1$$$, removing suffixes and adding an element to all suffixes. We can create a segment tree for minimum on $$$w$$$ in order to get the minimum on the removing segment. Let's maintain a mulitset of minimums on current suffixes. So, our queries are:
1. Add element $$$x$$$
2. Remove element $$$x$$$
3. For each element $$$a$$$ make $$$a = min(a, x)$$$
4. Get the sum of the elements
Let's store a map from an element to the number of its occurrences. Queries 1 and 2 can be done obviously. To perform the 3-rd query, we can just iterate through elements, which are bigger than $$$x$$$, remove them from the map, and add as many elements with value $$$x$$$. The amortized complexity of this solution is $$$O(n \log n)$$$.
BONUS: solve it when a suspiciousness of a "suspicious" segment is the $$$mex$$$ of elements instead of $$$min$$$.
Code (with BigInt realization)