自动搬运

查看原文

来自洛谷，原作者为

	Lagoon **

搬运于2025-08-24 22:22:35，当前版本为作者最后更新于2020-07-03 16:13:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先，根据runs的那套理论，位置不同的本原平方串（即最小整周期恰为 $len \over 2$ 的串）是 $O(n \log n)$ 的，显然所有平方串都是由某一个本原平方串复制若干遍得到的，然后我们先用传统的枚举周期SA/二分hash的方法求出若干的周期三元组 $(x,l,r)$ ，代表在区间 $[l,r]$ 中任意一个长为 $x$ 的倍数的子串整周期均为 $x$ ，然后如果串 $[l,l+2x-1]$ 是循环串，则 $x$ 不为最小整周期，那么这个周期三元组可以直接去掉。

然后我们考虑这一个周期三元组的贡献，我们记贡献组 $(x,y,v)$ 表示它对满足 $[x,y] \in [l',r']$ 的询问区间 $[l',r']$ 有 $v$ 的贡献。那么对于一个周期三元组 $(x,l,r)$ ，长度为 $2x$ 的平方串贡献就为 $(a,a+2x-1,1) , a \in [l,r-2x+1]$ 和 $(a,a+3x-1,-1) , a \in [l,r-3x+1]$ ，同理，长度为 $2kx$ 的平方串贡献为 $(a,a+2kx-1,1) , a \in [l,r-2kx+1]$ 和 $(a,a+(2k+1)x-1,-1) , a \in [l,r-(2k+1)x+1]$ ，根据runs那套理论，这显然是不超过 $O(n \log n)$ 的。

还有一种情况就是不同周期三元组之间可能产生相同的平方串，这种情况的处理是容易的：首先你从前到后考虑每个周期三元组，然后对每个周期三元组找出它包含的所有长度为 $2x$ 倍数的平方串（这和位置不同的本原平方串数量相等），然后找出它在这之前最后出现在哪里（在处理前面的时候记一下即可）还有在这个周期三元组第一次出现在哪里，然后把重复的贡献减掉即可。

然后对每个询问计算贡献就是一个斜线加矩形求和的二维数点，容易实现。

复杂度 $O(n \log^2 n)$ 。

代码（二分hash版本）

#include<bits/stdc++.h>
#define re register
#define ull unsigned long long
char ss[200100];
const ull base=61,inv=5745707170499696405llu;
ull hs[200100],ex[200100],rex[200100];
int n;
inline ull get(re int l,re int r)
{
	return hs[r]-hs[l-1]*ex[r-l+1];
}
inline bool equ(re int a,re int b,re int len)
{
	return get(a,a+len-1)==get(b,b+len-1);
}
int LCP(re int a,re int b)
{
	re int l=0,r=std::min(n-a+1,n-b+1);
	for(re int mid=(l+r+1)/2;l<r;mid=(l+r+1)/2)
	{
		if(equ(a,b,mid))l=mid;
		else r=mid-1;
	}
	return l;
}
int LCS(re int a,re int b)
{
	re int l=0,r=std::min(a,b);
	for(re int mid=(l+r+1)/2;l<r;mid=(l+r+1)/2)
	{
		if(equ(a-mid+1,b-mid+1,mid))l=mid;
		else r=mid-1;
	}
	return l;
}
std::vector<std::pair<int,int> >vc[200100],mc[200100];
std::vector<int>qry[400100];
int cnt,l[200100],r[200100],f[200100];
long long ans[200100];
std::unordered_map<ull,int>mp;
void add(re int x,re int ad)
{
	for(;x;x-=x&-x)f[x]+=ad;
}
struct par
{
	int x,y,v;
}pc1[10001000],pc2[10001000];
inline bool cmp(const par&A,const par&B){return A.x<B.x;}
int cct1,cct2; 
int qr(re int x)
{
	re int ans=0;
	for(;x<=n;x+=x&-x)ans+=f[x];
	return ans;
}
int ans1;
void adp(re int x1,re int x2,re int y1,re int y2,re int v)
{
	pc1[++cct1]={y1-x1,x1,v};
	pc1[++cct1]={y1-x1,x2+1,-v};
	pc2[++cct2]={y1-x1,y1,v};
	pc2[++cct2]={y1-x1,y2+1,-v};
}
int f1[200100],f2[200100];
void add1(re int a,re int ad)
{
	re int ad1=ad*a;
	for(;a<=n;a+=(a&-a))f1[a]+=ad,f2[a]+=ad1;//printf("**ad**%d\n",n);
}
long long sum(re int a)
{
	re int ans=0;
	re int a1=a;
	for(;a;a-=(a&-a))ans+=(a1+1)*f1[a]-f2[a];
	return ans;
}
int main()
{
	re int q,x,y;
	scanf("%d%d",&n,&q);
	scanf("%s",ss+1);
	ex[0]=rex[0]=1;
	for(re int i=1;i<=n;i++)hs[i]=hs[i-1]*base+(ss[i]-'a'+1),ex[i]=ex[i-1]*base,rex[i]=rex[i-1]*inv;
	for(re int i=1;i<=n;i++)
	{
		for(re int j=i;j+i<=n;j+=i)
		{
			re int ls=LCS(j,j+i),lp=LCP(j+1,j+i+1);
			if(ls==0||ls>i||ls+lp<i)continue;
			re int bg=j-ls+1,ed=j+i+lp;
			for(auto x:vc[bg])if((!(i%x.first))&&x.second>=i){ls=0;break;}
			if(ls==0)continue;
			for(re int i1=bg;i1+2*i-1<=ed;i1++)
			{
				vc[i1].push_back(std::make_pair(i,ed-i1+1));
				re ull nw=get(i1,i1+2*i-1);
				re int nv;
				if(!mp[nw])mp[nw]=++cnt;
				nv=mp[nw];
				re int len=(i1-bg)/i;
				if(!(len&1))
				{
					len=len/2;
					if(mc[nv].size()>len)
					{
						adp(mc[nv][len].first,mc[nv][len].first,i1+2*i-1,i1+2*i-1,-1);
						mc[nv][len]=std::make_pair(i1,i1+2*i-1);
					}
				}
			}
			for(re int i1=ed-2*i+1;i1>=bg;i1--)
			{
				re ull nw=get(i1,i1+2*i-1);
				re int nv;
				if(!mp[nw])mp[nw]=++cnt;
				nv=mp[nw];
				re int len=(ed-2*i+1-i1)/i;
				if(!(len&1))
				{
					len=len/2;
					if(mc[nv].size()>len)
					{
						mc[nv][len]=std::make_pair(i1,i1+2*i-1);
					}
					else mc[nv].push_back(std::make_pair(i1,i1+2*i-1));
				}
			}
			for(re int i1=0,vv=1;bg+i1+2*i-1<=ed;i1+=i,vv=-vv)
			{
				adp(bg,ed-i1-2*i+1,bg+i1+2*i-1,ed,vv);
			}
		}
	}
	for(re int i=1;i<=q;i++)
	{
		scanf("%d%d",&l[i],&r[i]);
		qry[r[i]-l[i]].push_back(i);
	}
	std::sort(pc1+1,pc1+cct1+1,cmp);
	std::sort(pc2+1,pc2+cct2+1,cmp);
	re int ta=1;
	for(re int i=0;i<=200000;i++)
	{
		while(ta<=cct1&&pc1[ta].x==i)
		{
		//	printf("**a**%d %d %d\n",i,pc1[ta].y,pc1[ta].v);
			add1(pc1[ta].y,pc1[ta].v);
			ta++;
		}
		for(auto x:qry[i])
		{
			ans[x]-=sum(l[x]-1);
		}
	}
	ta=1;
	memset(f1,0,sizeof(f1));
	memset(f2,0,sizeof(f2));
	for(re int i=0;i<=200000;i++)
	{
		while(ta<=cct2&&pc2[ta].x==i)
		{
			add1(pc2[ta].y,pc2[ta].v);
			ta++;
		}
		for(auto x:qry[i])
		{
			ans[x]+=sum(r[x]);
		}
	}
	for(re int i=1;i<=q;i++)printf("%lld\n",ans[i]);
}