题目链接
题目解法
牛题！
题目实际上是要每次加入一个字符，求所有的 \(border\) 的神秘度之和
考虑从前 \(i-1\) 个字符到前 \(i\) 个字符 \(border\) 的变化
如果 \(str_1=str_i\)，会加入长度为 \(1\) 的 \(border\)，这一部分可以暴力加
且只会保留 \(i-1\) 的 \(border\) 中，下一位和 \(str_i\) 相同的
我们考虑暴力删去所有不合法的 \(i-1\) 的 \(border\)，这一部分记录 \(to_{x,c}\) 表示 \([1,x]\) 的 \(border\) 中，最长的一个满足后一个字符为 \(c\) 的长度，就可以暴力跳了
因为每个 \(border\) 只会加一次，删一次，所以这部分的复杂度是可以接受的
现在考虑已经维护出了当前所有 \([1,i]\) 的 \(border\) 的除了 \(w_i\) 的神秘度
加入 \(w_i\) 相当于对每个值取 \(\min\) 操作
这部分暴力取出 \(>min\) 的值，删去其贡献即可
每次会把若干个不同的 \(>w_i\) 的数变成一个 \(w_i\)，所以复杂度是对的
时间复杂度 \(O(n\log n)\)
#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
typedef __int128_t i128;
const int N=600010;
int n,str[N],ne[N],to[N][26];
int st[N][20],lg[N];
i128 ans,res;
map<int,LL> mp;
int qry(int l,int r){
int k=lg[r-l+1];
return min(st[r][k],st[l+(1<<k)-1][k]);
}
void ins(int l,int r){
int val=qry(l,r);
mp[val]++,res+=val;
}
void del(int l,int r){
int val=qry(l,r);
mp[val]--,res-=val;
}
#define fi first
#define se second
void write(i128 x){
if(!x) return;
write(x/10),putchar(x%10+48);
}
int main(){
ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);
cin>>n;
F(i,2,n) lg[i]=lg[i>>1]+1;
int mx=0;
F(i,1,n){
char add;cin>>add;
str[i]=(add-'a'+ans)%26;
int w;cin>>w;
w^=(ans&((1<<30)-1));
st[i][0]=w;
F(j,1,lg[i]) st[i][j]=min(st[i][j-1],st[i-(1<<(j-1))][j-1]);
if(str[1]==str[i]) ins(i,i);
while(mx&&str[mx+1]!=str[i]) mx=ne[mx];
if(i>1&&str[mx+1]==str[i]) mx++;
ne[i]=mx;
F(j,0,25) to[i][j]=to[mx][j];
to[i][str[mx+1]]=mx;
F(j,0,25) if(j!=str[i]){
int cur=to[i-1][j];
while(cur) del(i-cur,i-1),cur=to[cur][j];
}
LL tms=0;
for(auto it=mp.upper_bound(w);it!=mp.end();){
res-=(i128)(it->fi-w)*it->se,tms+=it->se;
auto t=next(it);
mp.erase(it),it=t;
}
mp[w]+=tms;
ans+=res;
if(!ans) puts("0");
else write(ans),puts("");
}
return 0;
}