A13256. Fedya the Potter Strikes Back
编程题
普及/提高-
知识点
题目描述
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!
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!
输入格式
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$ .
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$ .
输出格式
Print $n$ lines, $i$ -th line should contain a single integer — the answer to the $i$ -th query.
输入输出样例
输入 #1
7 a 1 a 0 y 3 y 5 v 4 u 6 r 8
输出 #1
1 2 4 5 7 9 12
输入 #2
4 a 2 y 2 z 0 y 2
输出 #2
2 2 2 2
输入 #3
5 a 7 u 5 t 3 s 10 s 11
输出 #3
7 9 11 12 13
说明/提示
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$ .
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$ .