感觉是我结构体的问题,但找不出问题,呜呜呜。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int read()
{
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
const int MAXN=6e5+10,inf=1e18,MASK=(1<<30),mod=1e18;
char s[MAXN],t[30]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
int n,opt,val;
struct node
{
int x,y;
friend node operator +(node x,int y)
{
return {x.x+(x.y+y)/mod,(x.y+y)%mod};
}
friend int operator %(node x,int p)
{
return (x.y%p+x.x%p*mod%p)%p;
}
}ans;
int fa[MAXN][30];
int w[MAXN],f[MAXN],k=inf,op;
map<int,int>mp;
int net[MAXN],shu[MAXN*4];
int p[MAXN],tot;
void build(int now,int l,int r)
{
shu[now]=inf;
if(l==r)return;
int mid=(l+r)>>1;
build(now*2,l,mid);build(now*2+1,mid+1,r);
}
void change(int now,int l,int r,int x,int z)
{
if(l==r)
{
shu[now]=z;
return ;
}
int mid=(l+r)>>1;
if(x<=mid)change(now*2,l,mid,x,z);
else change(now*2+1,mid+1,r,x,z);
shu[now]=min(shu[now*2],shu[now*2+1]);
}
int query(int now,int l,int r,int x,int y)
{
if(x<=l&&r<=y)return shu[now];
int mid=(l+r)>>1;
int minx=inf;
if(x<=mid)minx=min(minx,query(now*2,l,mid,x,y));
if(mid<y)minx=min(minx,query(now*2+1,mid+1,r,x,y));
return minx;
}
void insert(int x,int y)
{
mp[x]+=y;val+=x*y;
}
int update(int x)
{
int cnt=0;
for(map<int,int>::iterator it=mp.upper_bound(x);it!=mp.end();it++)
val-=it->first*it->second,cnt+=it->second,p[++tot]=it->first;
for(int i=1;i<=tot;i++)mp.erase(p[i]);tot=0;
return cnt;
}
void add(int x)
{
change(1,1,n,x,w[x]);
int p=x-1;
while(p>0&&s[net[p]+1]!=s[x])p=net[p];
if(x!=1&&s[net[p]+1]==s[x])net[x]=net[p]+1;
if(s[x]==s[1])insert(w[x],1);
for(int i=0;i<26;i++)fa[x][i]=fa[net[x]][i];
fa[x][s[net[x]+1]-'a']=net[x];
for(int i=0;i<26;i++)
{
if(s[x]-'a'==i)continue;
for(int j=fa[x-1][i];j;j=fa[j][i])
insert(query(1,1,n,x-j,x-1),-1);
}
insert(w[x],update(w[x]));ans=ans+val;
}
char cz(int x,node y)
{
return t[(x+y%26)%26];
}
void write(node x)
{
if(x.x!=0)printf("%lld%018lld\n",x.x,x.y);
else printf("%lld\n",x.y);
}
signed main()
{
n=read();
for(int i=1;i<=n;i++)
{
s[i]=getchar();
s[i]=cz(s[i]-'a',ans);
w[i]=read();
w[i]^=(ans%MASK);
add(i);
write(ans);
}
return 0;
}