A了这道题，祝你们成功

不知道本题卡空间还是写错了？写的可持久化线段树合并，有这么写过的大佬吗。

我猜放一百多行代码没人看惹.

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define pre(i,a,b) for(int i=a;i>=b;i--)
#define N 1000005
using namespace std;
struct node{
	int l,r,sum;
	node(){l=r=sum=0;}
}a[N*30];
int tot;
int build(int l,int r,int pos){
	int x=++tot;a[x].sum=1;
	if(l==r)return x;
	int mid=(l+r)>>1;
	if(mid>=pos)a[x].l=build(l,mid,pos);
	else a[x].r=build(mid+1,r,pos);
	return x;
}
int merge(int x,int y,int l,int r){
	if(!x||!y)return x+y;
	int mid=(l+r)>>1,p=++tot;
	if(l==r){a[p].sum=a[x].sum+a[y].sum;return p;}
	a[p].l=merge(a[x].l,a[y].l,l,mid);
	a[p].r=merge(a[x].r,a[y].r,mid+1,r);
	a[p].sum=a[x].sum+a[y].sum;
	return p;
}
int ask(int x,int l,int r,int L,int R){
	if(!x)return 0;
	if(L<=l&&R>=r)return a[x].sum;
	int mid=(l+r)>>1,sum=0;
	if(mid>=L)sum+=ask(a[x].l,l,mid,L,R);
	if(mid<R)sum+=ask(a[x].r,mid+1,r,L,R);
	return sum;
}
int n;
struct SAM{
	int len[N],fa[N],nxt[N][26],rt[N],idx,pre,T,mat[N],b[N],c[N],del[N];
	SAM(){len[0]=idx=pre=T=0;fa[0]=~0;}
	void clean(int m){
		idx=pre=T=0;
		rep(i,0,(m<<1)){
			len[i]=fa[i]=rt[i]=mat[i]=b[i]=c[i]=del[i]=0;
			memset(nxt[i],0,sizeof(nxt[i]));fa[0]=~0;
		}
	}
	void extend(int ch,int type){
		int cur=++idx,p=pre;len[cur]=len[pre]+1;
		while(~p&&!nxt[p][ch])nxt[p][ch]=cur,p=fa[p];
		if(p==-1)fa[cur]=0;
		else{
			int q=nxt[p][ch];
			if(len[p]+1==len[q])fa[cur]=q;
			else{
				int now=++idx;len[now]=len[p]+1;
				rep(i,0,25)nxt[now][i]=nxt[q][i];
				fa[now]=fa[q];fa[q]=fa[cur]=now;
				while(~p&&nxt[p][ch]==q)nxt[p][ch]=now,p=fa[p];
			}
		}
		pre=cur;
		if(type)rt[cur]=build(1,n,++T);
		else mat[++T]=cur;
	}
	void init(){
		rep(i,1,idx)c[len[i]]++;
		rep(i,1,idx)c[i]+=c[i-1];
		rep(i,1,idx)b[c[len[i]]--]=i;
		pre(i,idx,1)rt[fa[b[i]]]=merge(rt[fa[b[i]]],rt[b[i]],1,n);
	}
	char s[N];
	bool check(int l,int r,int x,int ln){
		if(ln>(r-l+1))return false;
		return ask(rt[x],1,n,l+ln-1,r)?1:0;
	}
	void solve(){
		rep(i,1,idx)c[len[i]]++;
		rep(i,1,idx)c[i]+=c[i-1];
		rep(i,1,idx)b[c[len[i]]--]=i;
		long long ans=0;
		pre(i,idx,1){
			if(len[b[i]]>del[b[i]])ans+=(len[b[i]]-max(del[b[i]],len[fa[b[i]]]));
			del[fa[b[i]]]=max(del[fa[b[i]]],del[b[i]]);
		}//rep(i,1,idx)del[i]=0;
		printf("%lld\n",ans);
	}
}w,u;
char s[N];
void calc(){
	//cout<<"tt"<<endl;
	//cout<<"ss"<<endl;
	scanf("%s",s+1);
	int m=strlen(s+1);
	u.clean(m);
	rep(i,1,m)u.extend(s[i]-'a',0);
	//rep(i,1,m)printf("%d ",u.mat[i]);putchar('\n');
	int l,r;scanf("%d%d",&l,&r);
	int ln=0,now=0;
	rep(i,1,m){
		int op=s[i]-'a';
		while(now&&(!w.nxt[now][op]||!w.check(l,r,w.nxt[now][op],ln+1)))now=w.fa[now],ln=w.len[now];
		if(w.nxt[now][op]&&w.check(l,r,w.nxt[now][op],ln+1))now=w.nxt[now][op],ln++;
		//cout<<i<<" "<<ln<<endl;
		u.del[u.mat[i]]=ln;
	}
	u.solve();
}
int main(){
	//freopen("input","r",stdin);
	scanf("%s",s+1);
	n=strlen(s+1);
	rep(i,1,n)w.extend(s[i]-'a',1);
	//cout<<"ss"<<endl;
	w.init();
	//cout<<"tt"<<endl;
	int q;scanf("%d",&q);
	//cout<<"uu"<<endl;
	//cout<<n<<" "<<q<<" "<<s+1<<endl;
	while(q--)calc();
	return 0;
}
/*
g++ 4770.cpp -o a -Wall -std=c++11
*/