RT，第二个点挂了，开 O2 就显示炸空间

#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
#define int long long
const int N=1e5+10,INF=0x3f3f3f3f3f3f3f3f;
struct smt_node{
	int val,tag;
};
smt_node smt[4*N];
inline void smt_pushup(int now){
	int ls=now<<1,rs=now<<1|1;
	smt[now].val=smt[ls].val+smt[rs].val;
}
inline void smt_pushdown(int now,int l,int r){
	if(!smt[now].val) return ;
	int ls=now<<1,rs=now<<1|1;
	int mid=l+r>>1,l1=mid-l+1,l2=r-mid;
	smt[ls].tag+=smt[now].tag;
	smt[ls].val+=smt[now].tag*l1;
	smt[rs].tag+=smt[now].tag;
	smt[rs].val+=smt[now].tag*l2;
	smt[now].tag=0;
}
void smt_modify(int now,int l,int r,int ml,int mr,int val){
	if(l>=ml&&r<=mr){
		smt[now].tag+=val;
		smt[now].val+=val*(r-l+1);
		return ;
	}
	smt_pushdown(now,l,r);
	int mid=l+r>>1;
	if(ml<=mid) smt_modify(now<<1,l,mid,ml,mr,val);
	if(mr>mid) smt_modify(now<<1|1,mid+1,r,ml,mr,val);
	smt_pushup(now);
}
int smt_query(int now,int l,int r,int ql,int qr){
	if(l>=ql&&r<=qr) return smt[now].val;
	smt_pushdown(now,l,r);
	int mid=l+r>>1,ans=0;
	if(ql<=mid) ans+=smt_query(now<<1,l,mid,ql,qr);
	if(qr>mid) ans+=smt_query(now<<1|1,mid+1,r,ql,qr);
	return ans;
}
struct spl_node{
	int fa,son[2];
	int mxn,mnn;
	int mx,mn;
	int col;
};
spl_node spl[2*N];
int len;
inline bool check_root(int now){
	return spl[spl[now].fa].son[0]!=now&&spl[spl[now].fa].son[1]!=now;
}
inline int relation(int fa,int now){
	return spl[fa].son[1]==now;
}
inline int connect(int fa,int now,int son){
	spl[fa].son[son]=now,spl[now].fa=fa;
}
inline void spl_pushup(int now){
	int ls=spl[now].son[0],rs=spl[now].son[1];
	spl[now].mn=min(spl[now].mnn,min(spl[ls].mn,spl[rs].mn));
	spl[now].mx=max(spl[now].mxn,min(spl[ls].mx,spl[rs].mx));
}
inline void spl_pushdown(int now){
	int ls=spl[now].son[0],rs=spl[now].son[1];
	spl[ls].col=spl[rs].col=spl[now].col;
}
inline void spl_pushall(int now){
	if(!check_root(now))
		spl_pushall(spl[now].fa);
	spl_pushdown(now);
}
void rotate(int now){
	int fa=spl[now].fa,gf=spl[fa].fa;
	int r1=relation(fa,now),r2=relation(gf,fa);
	connect(fa,spl[now].son[r1^1],r1),connect(now,fa,r1^1);
	if(spl[gf].son[r2]==fa) spl[gf].son[r2]=now;
	spl[now].fa=gf,spl_pushup(fa),spl_pushup(now);
}
void splaying(int now){
	spl_pushall(now);
	while(!check_root(now)){
		int fa=spl[now].fa,gf=spl[fa].fa;
		int r1=relation(fa,now),r2=relation(gf,fa);
		if(!check_root(fa)) r1^r2?rotate(fa):rotate(now);
		rotate(now);
	}
}
void access(int now,int pos){
	int son=0;
	while(now){
		splaying(now);
		int col=spl[now].col,ml=col-spl[now].mx+1,mr=col-spl[now].mn+1;
		if(pos!=col&&col) smt_modify(1,1,len,ml,mr,-1);
		spl[now].son[1]=son,spl_pushup(now);
		son=now,now=spl[now].fa;
	}
}
void link(int x,int y){
	spl[y].fa=x;
}
void cut(int x,int y){
	splaying(y),splaying(x);
	if(!check_root(y)) spl[x].son[1]=y;
	spl[y].fa=0;
}
struct prt_node{
	int len,fa;
	int val;
};
struct suffix_automaton{
	prt_node prt[2*N];
	int ch[2*N][26];
	int last,tot;
	suffix_automaton(){
		last=tot=1;
	}
	void add(int c,int col){
		int p=last,np=last=++tot;
		prt[np].len=prt[p].len+1;
		smt_modify(1,1,len,1,col,1);
		while(p&&!ch[p][c]){
			ch[p][c]=np;
			p=prt[p].fa;
		}
		if(!p){
			prt[np].fa=1;
			spl[np].col=col;
			spl[np].mn=spl[np].mnn=prt[1].len+1;
			spl[np].mx=spl[np].mxn=prt[np].len;
			link(1,np),access(np,col),splaying(np);
			spl[np].col=col;
			return ;
		}
		int q=ch[p][c];
		if(prt[q].len==prt[p].len+1){
			prt[np].fa=q;
			spl[np].col=col;
			spl[np].mn=spl[np].mnn=prt[q].len+1;
			spl[np].mx=spl[np].mxn=prt[np].len;
			link(q,np),access(np,col),splaying(np);
			spl[np].col=col;
			return ;
		}
		int nq=++tot,fa=prt[q].fa;
		prt[nq].len=prt[p].len+1;
		prt[nq].fa=fa,prt[np].fa=prt[q].fa=nq;
		spl[nq].mn=spl[nq].mnn=prt[fa].len+1;
		spl[nq].mx=spl[nq].mxn=prt[nq].len;
		spl[np].mn=spl[np].mnn=prt[nq].len+1;
		spl[np].mx=spl[np].mxn=prt[np].len;
		splaying(q),spl[q].mnn=prt[nq].len+1,spl_pushup(q);
		spl[np].col=col,spl[nq].col=spl[q].col;
		cut(fa,q),link(fa,nq),link(nq,q),link(nq,np);
		access(np,col),splaying(np);
		spl[np].col=spl[nq].col=col;
		for(int i=0;i<26;i++) ch[nq][i]=ch[q][i];
		while(p&&ch[p][c]==q){
			ch[p][c]=nq;
			p=prt[p].fa;
		}
	}
};
suffix_automaton sam;
struct quest{
	int l,r;
	int pos;
};
quest que[2*N];
inline bool cmp(quest x,quest y){
	return x.r<y.r;
}
string s;
int ans[2*N];
signed main(){
	for(int i=0;i<2*N;i++){
		spl[i].mn=spl[i].mnn=INF;
		spl[i].mx=spl[i].mxn=-INF;
	}
	cin>>s;
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>que[i].l>>que[i].r;
		que[i].pos=i;
	}
	sort(que+1,que+n+1,cmp);
	len=s.size();
	for(int i=0,j=1;i<=len-1;i++){
		sam.add(s[i]-'a',i+1);
		while(que[j].r==i+1){
			int l=que[j].l,r=que[j].r;
			ans[que[j++].pos]=smt_query(1,1,len,l,r);
		}
	}
	for(int i=1;i<=n;i++) cout<<ans[i]<<'\n';
}