求助 wa 在190个点,寄
查看原帖
求助 wa 在190个点,寄
177604
LXH5514楼主2022/7/25 12:40

感觉是我结构体的问题,但找不出问题,呜呜呜。

#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;
}
2022/7/25 12:40
加载中...