Fedya the Potter Strikes Back
题意翻译
给定一个字符串 $S$ 和一个序列 $W$，初始时它们都为空。
你需要在线完成 $n$ 次操作。每次操作在 $S$ 后面添加一个字符 $c$，在序列 $W$ 后面添加一个数字 $W_i$。二者均加密。加密规则如下：
设 $ans$ 为上一个查询的答案（$ans$ 初始值为 $0$）。
$c$ 等于 $ci$ 按字典序后移 $ans$ 位，$w$ 等于 $wi\ \oplus ({ans\ \&\ MASK})$， $MASK\ = 2^{30}\ -\ 1$。（特别地，定义 $z + 1 = a$）
定义一个子区间 $[L,R]$ 的可疑度为：
若子串 $[L,R]$ 和前缀 $[1,R-L+1]$ 相同，则其可疑度为 $min_{i=L}^{R} W_i$。否则其可疑度为 $0$。
每次操作后，你都要求出当前的串的所有子区间的可疑度之和。
题目描述
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!
输入输出格式
输入格式
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 $ .
输出格式
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 $ .