状态:#19~20,22~25TLE

时间复杂度没问题,本地测试答案正确(23.793s),但就是卡不进5s的时间限制。求助。

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
struct xyq{ //后缀排序需要用到的桶。链表存储。
	int a,next;
}_[10000555];
int head[2000005],noi=1;
inline void add(int id,int a){
	_[noi].a=a;
	_[noi].next=head[id];
	head[id]=noi;
	++noi;
}
int sa[8000555],Rank[8000555][2],ran[3000555],a[8000555],tot=0,h[3000555],height[3000555],mi[21][5005555],lcp[8000555],log2[8000555]; //start:每个字符串的开始位置。zyl:拼接串每个字符对应哪个限制串。 
inline int query(int l,int r){
	if(l>r){
		return 2147483647;
	}
	int ykb=log2[r-l+1];
	return min(mi[ykb][l],mi[ykb][r-(1<<ykb)+1]);
}
int n;
struct question{ //询问。 
	string s;
	int l,r,id;
}que[3005555];
struct hEadmAstErtRee{
	int l,r,val;
}qwer[80055555];
int node=0,leaf[3005555],root[3055555];
inline void make(int id,int last,int l,int r,int addid){
	qwer[id].val=qwer[last].val+1;
	if(l>=r){
		return;
	}
	int mid=l+r>>1;
	if(addid<=mid){
		qwer[id].l=node++;
		qwer[id].r=qwer[last].r;
		make(qwer[id].l,qwer[last].l,l,mid,addid);
	}else{
		qwer[id].l=qwer[last].l;
		qwer[id].r=node++;
		make(qwer[id].r,qwer[last].r,mid+1,r,addid);
	}
}
inline int ask(int id,int nowl,int nowr,int ql,int qr){
	if(nowl>=ql&&nowr<=qr){
		return qwer[id].val;
	}
	if(qr<nowl||ql>nowr){
		return 0;
	}
	int mid=nowl+nowr>>1;
	return ask(qwer[id].l,nowl,mid,ql,qr)+ask(qwer[id].r,mid+1,nowr,ql,qr);
}
inline bool kmp(int l1,int r1,int l2,int r2){ //s[l1,r1]为主串,s[l2,r2]为模式串。进行匹配,返回可以匹配出多少个。
	int lid=1,rid=ran[l2],mid,lj=-1,rj=-1,len=r2-l2+1;
	while(lid<=rid){
		mid=lid+rid>>1;
		if(query(mid+1,ran[l2])>=len){
			lj=mid;
			rid=mid-1;
		}else{
			lid=mid+1;
		}
	}
	lid=ran[l2];
	rid=n-1;
	while(lid<=rid){
		mid=lid+rid>>1;
		if(query(ran[l2]+1,mid)>=len){
			rj=mid;
			lid=mid+1;
		}else{
			rid=mid-1;
		}
	}
	return ask(root[rj],0,n,l1,r1-len+1)-ask(root[lj-1],0,n,l1,r1-len+1);
}
inline int max(int a,int b){
	return (a>b)?a:b;
}
inline int min(int a,int b){
	return (a>b)?b:a;
}
int zxcv[5000005],zyl[5000005],start[5000555];
int main(){
	freopen("P4770_7.in","r",stdin);
	freopen("0.out","w",stdout);
	string s,ion2017;
	cin>>ion2017;
	s=ion2017+'^';
	int i,j,k,logn,ykb,last,m,now,maxl,minr,lj,rj,q;
	long long sum=0;
	cin>>q;
	//1.将所有限制字符串拼接,用'^'拼接两个字符串。 
	for(register int i(0);i<q;++i){
		cin>>que[i].s;
		scanf("%d %d",&que[i].l,&que[i].r);
		--que[i].l;
		--que[i].r;
		start[i]=s.size();
		s.insert(s.size(),que[i].s);
		s.insert(s.size(),1,'^');
		que[i].id=i;
	}
	//2.求出后缀数组rank及sa。 
	n=s.size();
	start[q]=n;
	for(logn=0;(1<<logn)<n;logn++);
	for(register int i(0);i<n;++i){
		Rank[i][0]=s[i];
	}
	ykb=max(127,n+1);
	for(register int i(1);i<=logn;++i){
		for(register int j(0);j<n;++j){//第一轮按第二关键字排序。
			add(Rank[j+(1<<i-1)][!(i&1)],j);
		}
		tot=0;
		for(register int j=ykb;j>=0;j--){//取桶,放入a数组。
			for(register int k=head[j];k;k=_[k].next){
				a[tot++]=_[k].a;
			}
		}
		noi=1;
		memset(head,0,sizeof(head));
		for(register int j(0);j<n;++j){ //第二轮排序,从a中的数找。
			add(Rank[a[j]][!(i&1)],a[j]);
		}
		tot=0;
		for(register int j(0);j<ykb;++j){
			last=0;
			for(register int k=head[j];k;k=_[k].next){
				if(!last||Rank[_[k].a+(1<<i-1)][!(i&1)]!=Rank[_[last].a+(1<<i-1)][!(i&1)]){
					++tot;
				}
				last=k;
				Rank[_[k].a][i&1]=tot;
			}
		}
		noi=1;
		memset(head,0,sizeof(head));
	}
	for(register int i(0);i<n;++i){
		ran[i]=Rank[i][logn&1]-1;
		sa[ran[i]]=i;
	}
	for(register int i(0);i<q;++i){ //求出zyl。
		for(register int j=start[i];j<start[i+1];++j){
			zyl[j]=i;
		}
	}
	//-------------------------------------3.求出height。 ---------------------------------------
	j=0;
	for(register int i(0);i<n;++i){
		if(j){
			--j;
		}
		while(ran[i]&&s[i+j]==s[sa[ran[i]-1]+j]){
			++j;
		}
		h[i]=j;
	}
	for(register int i(0);i<n;++i){
		height[ran[i]]=h[i];
	}
	now=0;
	//---------------------------------------4.主席树预处理。------------------------------------- 
	for(register int i(1);i<(n<<1);++i){
		qwer[i].l=i<<1;
		qwer[i].r=(i<<1)|1;
	}
	node=n<<2;
	for(register int i(0);i<n;++i){
		if(sa[i]<start[0]-1){
			root[i]=node++;
			make(root[i],i?root[i-1]:1,0,n,sa[i]);
		}else{
			root[i]=(i?root[i-1]:0);
		}
	}
	//-----------------------------5.rmq预处理。mi[i][j]表示j..j+pow(2,i)的最小值。------------------------------- 
	for(register int i(0);i<n;++i){
		mi[0][i]=height[i];
	}
	for(register int i(1);i<=logn;++i){
		for(register int j(0);j<n;++j){
			mi[i][j]=min(mi[i-1][j],mi[i-1][j+(1<<i-1)]);
		}
	}
	log2[1]=0;
	for(register int i(2);i<=n;++i){
		log2[i]=log2[i>>1]+1;
	}
	//----------------------------------------6.注意去重,求出与上一位的最长公共前缀,若上一位不是原串(即为限制串)中的,继续往前一位,并累计min。---------------------------------------------
	last=2147483647;
	for(register int i(0);i<n;++i){ //枚举排名。 
		if(s[sa[i]]=='^'||sa[i]<start[0]){
			continue;
		}
		lcp[i]=query(zxcv[zyl[sa[i]]]+1,i);
		zxcv[zyl[sa[i]]]=i;
	}
	//8.枚举左端点i,求出右端点j的可行区间[lj,rj]。(单调性实现)
	for(register int i(0);i<q;++i){
		lj=0;
		sum=0;
		for(register int j=start[i];j<start[i+1]-1;++j){ //枚举左端点。 
			lj=max(lj,j);
			while(lj<start[i+1]-1&&kmp(que[i].l,que[i].r,j,lj)){ //枚举到可满足要求。
				++lj;
			}
			sum+=(long long)(start[i+1]-max(lj,j+lcp[ran[j]])-1);
		}
		cout<<sum<<endl;
	}
	return 0;
}