考虑在每次加入一个字符后，求出所有合法后缀（即 border）的权值和。容易想到用 KMP 算法解决。
具体的，我们维护 border 的集合。加入一个字符 \(c_i\) 后，对集合的改变为：
- 如果一个 border 对应前缀的下一个字符不是 \(c\)，将其删除。
- 如果 \(c_i=c_0\)，加入长度为 \(1\) 的 border。
由于最多加入 \(n\) 个 border，所以每次操作删除的 border 个数是均摊 \(\mathcal O(1)\) 的。
我们考虑如何快速找到被删除的 border。由于这些 border 都在 KMP 算法中从 \(i\) 到 \(0\) 的路径上（即 \(i,\operatorname{next}_i,\operatorname{next}_{\operatorname{next}_i},\cdots,0\)），我们对每一个节点记录其第一个后继字符不一样的祖先，这样我们就能在 \(\mathcal O(1)\) 时间内找到下一个被删除的 border。根据上面的分析，这样的复杂度是均摊 \(\mathcal O(1)\) 的。
最后是权值的处理。在删除一个 border 时，需要询问它的权值，可以通过单调栈 + 二分解决。还需要把所有大于 \(w_i\) 的权值修改为 \(w_i\)，我们使用 map 维护每个权值以及出现次数，修改时暴力找到所有大于 \(w_i\) 的权值，因为每个值只会被后面的数暴力取 \(\min\) 一次，所以这样的复杂度是均摊 \(\mathcal O(\log n)\) 的。
总时间复杂度：\(\mathcal O(n\log n)\)。
以及要开 __int128。
Code：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
int ans26, ansB; __int128 ans;
string s;
char c;
vector <int> anc, nxt, w, stk{0};
map <int, int> cnt;
void print(__int128 x) {
if (x > 9) print(x / 10);
putchar(x % 10 + '0');
}
int query(int x) {
return w[*lower_bound(stk.begin(), stk.end(), x)];
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n, anc.resize(n + 1), nxt.resize(n + 1), w.resize(n + 1);
cin >> c >> w[0];
s += c, ans26 = w[0] % 26, ans = ansB = w[0];
print(ans), printf("\n");
ll sum = 0;
for (int i = 1, j = 0; i < n; ++i) {
cin >> c >> w[i];
c = (c - 'a' + ans26) % 26 + 'a', s += c;
w[i] ^= ansB;
while (j > 0 && s[j] != c) j = nxt[j];
if (s[j] == c) ++j;
nxt[i + 1] = j;
if (s[nxt[i]] == c) anc[i] = anc[nxt[i]];
else anc[i] = nxt[i];
for (int k = i; k > 0; ) {
if (s[k] == c) k = anc[k];
else {
int v = query(i - k);
--cnt[v], sum -= v;
if (!cnt[v]) cnt.erase(v);
k = nxt[k];
}
}
if (s[0] == c) ++cnt[w[i]], sum += w[i];
while (!stk.empty() && w[i] <= w[stk.back()]) stk.pop_back();
stk.push_back(i);
int t = 0;
for (auto it = cnt.upper_bound(w[i]); it != cnt.end(); ) {
sum -= 1ll * (it -> first - w[i]) * it -> second, t += it -> second;
auto j = next(it); cnt.erase(it), it = j;
}
cnt[w[i]] += t;
ll cur = w[stk[0]] + sum;
ans += cur;
ans26 = (ans26 + cur) % 26, ansB = (ansB + cur) & ((1 << 30) - 1);
print(ans), printf("\n");
}
return 0;
}