CF1286E Fedya the Potter Strikes Back

Fedya 有一个字符串 $S$，初始为空，还有一个数组 $W$，也初始为空。 现在有 $n$ 个操作需要依次处理。第 $i$ 个操作包含一个小写英文字母 $c_i$ 和一个非负整数 $w_i$。首先，将 $c_i$ 添加到 $S$ 的末尾，将 $w_i$ 添加到 $W$ 的末尾。该操作的答案为 $W$ 所有子区间 $[L,\,R]$（$1 \leq L \leq R \leq i$）的可疑度之和。 我们定义一个子区间的可疑度如下：如果 $S$ 中对应该子区间的子串（即从第 $L$ 个字符到第 $R$ 个字符的连续子串）等于 $S$ 的相同长度的前缀（即 $S$ 的前 $R-L+1$ 个字符），那么该子区间的可疑度等于 $W$ 在 $[L,\,R]$ 区间上的最小值。否则，如果子串与对应前缀不相等，则该子区间的可疑度为 $0$。 请帮助 Fedya 回答所有操作的结果，赶在护工来之前！

第一行包含一个整数 $n$（$1 \leq n \leq 600\,000$），表示操作数。 接下来的 $n$ 行，第 $i$ 行包含一次操作：一个小写拉丁字母 $c_i$ 和一个整数 $w_i$（$0 \leq w_i \leq 2^{30} - 1$）。 所有操作均以加密形式给出。设 $ans$ 为上一次操作的答案（对于第一次操作，$ans=0$）。则真实的操作需要如下解密：将 $c_i$ 在字母表中循环向前移动 $ans$ 位，将 $w_i$ 设为 $w_i \oplus (ans\,\&\,MASK)$，其中 $\oplus$ 表示按位异或，$\&$ 表示按位与，$MASK=2^{30}-1$。

输出 $n$ 行，第 $i$ 行输出第 $i$ 次操作的答案。

为方便起见，我们称那些对应子串为 $S$ 前缀的子区间为“可疑”子区间，即其可疑度可能不为零的子区间。 在第一个样例中，解密后 $S$ 为 "abacaba"，所有 $w_i=1$，即所有可疑子区间的可疑度均为 $1$。下面说明每次操作后的答案： 1. $S$ = "a"，$W$ 只有一个子区间 $[1,\,1]$，对应子串为 "a"，即整个 $S$，是 $S$ 的前缀，可疑度为 $1$。 2. $S$ = "ab"，可疑子区间有 $[1,\,1]$ 和 $[1,\,2]$，总和为 $2$。 3. $S$ = "aba"，可疑子区间有 $[1,\,1]$、$[1,\,2]$、$[1,\,3]$ 和 $[3,\,3]$，总和为 $4$。 4. $S$ = "abac"，可疑子区间有 $[1,\,1]$、$[1,\,2]$、$[1,\,3]$、$[1,\,4]$ 和 $[3,\,3]$，总和为 $5$。 5. $S$ = "abaca"，可疑子区间有 $[1,\,1]$、$[1,\,2]$、$[1,\,3]$、$[1,\,4]$、$[1,\,5]$、$[3,\,3]$ 和 $[5,\,5]$，总和为 $7$。 6. $S$ = "abacab"，可疑子区间有 $[1,\,1]$、$[1,\,2]$、$[1,\,3]$、$[1,\,4]$、$[1,\,5]$、$[1,\,6]$、$[3,\,3]$、$[5,\,5]$ 和 $[5,\,6]$，总和为 $9$。 7. $S$ = "abacaba"，可疑子区间有 $[1,\,1]$、$[1,\,2]$、$[1,\,3]$、$[1,\,4]$、$[1,\,5]$、$[1,\,6]$、$[1,\,7]$、$[3,\,3]$、$[5,\,5]$、$[5,\,6]$、$[5,\,7]$ 和 $[7,\,7]$，总和为 $12$。 在第二个样例中，解密后 $S$ = "aaba"，$W = [2, 0, 2, 0]$。 1. $S$ = "a"，可疑子区间：$[1,\,1]$（可疑度 $2$），总和 $2$。 2. $S$ = "aa"，可疑子区间：$[1,\,1]$（$2$）、$[1,\,2]$（$0$）、$[2,\,2]$（$0$），总和 $2$。 3. $S$ = "aab"，可疑子区间：$[1,\,1]$（$2$）、$[1,\,2]$（$0$）、$[1,\,3]$（$0$）、$[2,\,2]$（$0$），总和 $2$。 4. $S$ = "aaba"，可疑子区间：$[1,\,1]$（$2$）、$[1,\,2]$（$0$）、$[1,\,3]$（$0$）、$[1,\,4]$（$0$）、$[2,\,2]$（$0$）、$[4,\,4]$（$0$），总和 $2$。 在第三个样例中，解密后 $S$ = "abcde"，$W = [7, 2, 10, 1, 7]$。 1. $S$ = "a"，可疑子区间：$[1,\,1]$（$7$），总和 $7$。 2. $S$ = "ab"，可疑子区间：$[1,\,1]$（$7$）、$[1,\,2]$（$2$），总和 $9$。 3. $S$ = "abc"，可疑子区间：$[1,\,1]$（$7$）、$[1,\,2]$（$2$）、$[1,\,3]$（$2$），总和 $11$。 4. $S$ = "abcd"，可疑子区间：$[1,\,1]$（$7$）、$[1,\,2]$（$2$）、$[1,\,3]$（$2$）、$[1,\,4]$（$1$），总和 $12$。 5. $S$ = "abcde"，可疑子区间：$[1,\,1]$（$7$）、$[1,\,2]$（$2$）、$[1,\,3]$（$2$）、$[1,\,4]$（$1$）、$[1,\,5]$（$1$），总和 $13$。 由 ChatGPT 4.1 翻译