代码

#include<bits/stdc++.h>
using namespace std;

template <typename T> void chmin(T &x,const T &y)
{
	if(x>y)x=y;
}
template <typename T> void chmax(T &x,const T &y)
{
	if(x<y)x=y;
}
typedef long long s64;
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)
const int N=5e5+1e6+1e5+5;
int s[N],sa[N],qa[2][N],*rk=qa[0],*tmp=qa[1],tot;
int reads()
{
	string str;
	cin>>str;
	int n=str.size();
	rep(i,1,n)s[tot+i]=str[i-1]-'a'+1;
	tot+=n+1;
	s[tot]=26+tot;	
	return n;
}
int cnt[N+26],h[N];
void init_sa(int n)
{
	rep(i,1,n)++cnt[s[i]];
	rep(i,1,n+26)cnt[i]+=cnt[i-1];
	rep(i,1,n)sa[cnt[s[i]]--]=i;
	rk[sa[1]]=1;
	rep(i,2,n)rk[sa[i]]=rk[sa[i-1]]+(s[sa[i]]!=s[sa[i-1]]);
	for(int l=1;rk[sa[n]]<n;l<<=1)
	{
		int top=0;
		rep(i,n-l+1,n)tmp[++top]=i;
		rep(i,1,n)
		if(sa[i]>l)tmp[++top]=sa[i]-l;
		
		rep(i,1,rk[sa[n]])cnt[i]=0;
		rep(i,1,n)++cnt[rk[i]];
		rep(i,1,rk[sa[n]])cnt[i]+=cnt[i-1];
		per(i,n,1)
		{
			int x=tmp[i];
			sa[cnt[rk[x]]--]=x;
		}
		
		swap(tmp,rk);
		rk[sa[1]]=1;
		rep(i,2,n)rk[sa[i]]=rk[sa[i-1]]+(tmp[sa[i]]!=tmp[sa[i-1]]||tmp[sa[i]+l]!=tmp[sa[i-1]+l]);
	}
	rep(i,1,n)
	{
		int l=max(0,h[rk[i-1]]-1);
		while(s[i+l]==s[sa[rk[i]+1]+l])++l;
		h[rk[i]]=l;
	}
}
#define cl (i*2)
#define cr (cl+1)
namespace ZKW
{
const int T=N*3;
int n,d;
int mnh[T];
namespace T1
{
int mni[T];
void add(int i,int x)
{
	for(i+=d;mni[i]>x;i>>=1)mni[i]=x;
}
int pre_(int i,int r)
{
	int lcp=n,ans=0;
	for(i+=d;i>1;i>>=1)
	if(i%2)
	{
		if(!(r-mni[i-1]+1>=min(lcp,mnh[i-1])))
		{
			chmax(ans,r-mni[i-1]+1);
			chmin(lcp,mnh[i-1]);
			continue;
		}
		--i;
		while(i<=d)
		if(r-mni[cr]+1>=min(lcp,mnh[cr]))
		{
			i=cr;	
		}
		else
		{
			i=cl;
			chmax(ans,r-mni[i+1]+1);
			chmin(lcp,mnh[i+1]);
		}
		return max(ans,min(min(lcp,mnh[i]),r-mni[i]+1));
	}
	return ans;
}
int suf_(int i,int r)
{
	i+=d;
	int lcp=mnh[i],ans=0;
	for(;i>1;i>>=1)
	if(i%2==0)
	{
		if(!(r-mni[i+1]+1>=min(lcp,mnh[i+1])))
		{
			chmax(ans,r-mni[i+1]+1);
			chmin(lcp,mnh[i+1]);
			continue;
		}
		++i; 
		while(i<=d)
		if(r-mni[cl]+1>=min(lcp,mnh[cl]))
		{
			i=cl;	
		}
		else
		{
			i=cr;
			chmax(ans,r-mni[i-1]+1);
			chmin(lcp,mnh[i-1]);
		}
		return max(ans,min(lcp,r-mni[i]+1));
	}
	return ans;
}
int qiu(int i,int r)
{
//	cerr<<pre_(i,r)<<endl;
//	cerr<<suf_(i,r)<<endl;
	return max(pre_(i,r),suf_(i,r));
}
};
namespace T2
{
bool mark[T];	
void add(int i,bool w)
{
	for(i+=d;i;i>>=1)mark[i]=w;
}
int pre_(int i)
{
	int ans=n;
	for(i+=d;i>1;i>>=1)
	if(i%2)
	{
		if(!mark[i-1]){chmin(ans,mnh[i-1]);continue;}
		--i;
		while(i<=d)
		if(mark[cr])i=cr;
		else
		{
			i=cl;chmin(ans,mnh[i+1]);
		}
		return min(ans,mnh[i]);
	}
	return 0;
}
int suf_(int i)
{
	i+=d;
	int ans=mnh[i];
	for(;i>1;i>>=1)
	if(i%2==0)
	{
		if(!mark[i+1]){chmin(ans,mnh[i+1]);continue;}
		--i;
		while(i<=d)
		if(mark[cl])i=cl;
		else
		{
			i=cr;chmin(ans,mnh[i-1]);
		}
		return ans;
	}
	return 0;
}
int qiu(int i)
{
	return max(pre_(i),suf_(i));
}
};
void init(int _n)
{
	n=_n;
	d=1;
	while(d<=n)d*=2;
	--d;
	rep(i,1,n){mnh[i+d]=h[i];T1::mni[i+d]=n+1;}
	per(i,d,1)
	{
		mnh[i]=min(mnh[cl],mnh[cr]);
		T1::mni[i]=n+1;
	}
}
};
 
int t[N];
const int M=1e5+5; 
struct Query
{
	int fir,len,r,next;s64 ans;
};
Query query[M];
s64 solve(const Query &x)
{
	s64 ans=0;
	rep(i,1,x.len)
	{
		int id=rk[x.fir+i];
//		cerr<<ZKW::T1::qiu(id,x.r)<<endl;
//		cerr<<ZKW::T2::qiu(id)<<endl;
		ans+=x.len-i+1 -max(ZKW::T1::qiu(id,x.r),ZKW::T2::qiu(id));
		ZKW::T2::add(id,1);
	}
	rep(i,1,x.len)ZKW::T2::add(rk[x.fir+i],0);
	return ans;
}

int main()
{
	freopen("1.in","r",stdin);
	int n=reads();
	int m;cin>>m;
	rep(i,1,m)
	{
		query[i].fir=tot;
		query[i].len=reads();
		int l;
		scanf("%d%d",&l,&query[i].r);
		query[i].next=t[l];t[l]=i;
	}
	init_sa(tot);
	ZKW::init(tot);
	per(l,n,1)
	{
		ZKW::T1::add(rk[l],l);	
		for(int i=t[l];i;i=query[i].next)query[i].ans=solve(query[i]);
	}
	rep(i,1,m)printf("%lld\n",query[i].ans); 
}

评测结果