之前做过 事情的相似度 那题有点LCT维护parent树的经验，但是这题要么0pts要么20pts，对着@灵梦 的代码改了改，还是RE 20ptsOrz。

有没有神仙帮我看看Orz.

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
typedef long long ll;
typedef unsigned un;
//typedef std::string str;
typedef std::pair<ll,ll> pll;
typedef std::pair<int,int> pii;
typedef std::pair<double,double> pd;
ll read(){ll x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return f*x;}
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
void umax(int& a,int t){if(t>a)a=t;}
bool umin(int& a,int t){if(t<a)return a=t,1;return 0;}
#define MAXN 400011
int n;
struct SAM
{
    int t[MAXN][2],pre[MAXN],len[MAXN];
    int tot,last;
    SAM(){last=tot=1;}
    void insert(int w)
    {
        int pos=last,cur=++tot;
        len[cur]=len[pos]+1,last=cur;
        while(pos&&!t[pos][w])t[pos][w]=cur,pos=pre[pos];
        if(!pos){pre[cur]=1;return;}
        int nxt=t[pos][w];
        if(len[nxt]==len[pos]+1)pre[cur]=nxt;
        else
        {
            int tmp=++tot;
            len[tmp]=len[pos]+1;
            memcpy(t[tmp],t[nxt],sizeof t[nxt]);
            pre[tmp]=pre[nxt],pre[nxt]=pre[cur]=tmp;
            while(pos&&t[pos][w]==nxt)t[pos][w]=tmp,pos=pre[pos];
        }
    }
}sam;
struct Segment_Tree
{
    struct node
    {
        ll tag,sum;
    }t[MAXN<<2|1];
    #define rt t[num]
    #define tl t[num<<1]
    #define tr t[num<<1|1]
    void pushdown(un l,un r,un num)
    {
        if(!rt.tag)return;
        un mid=(l+r)>>1;
        tl.sum+=(mid-l+1)*rt.tag,tl.tag+=rt.tag;
        tr.sum+=(r-mid)*rt.tag,tr.tag+=rt.tag;
        rt.tag=0;
    }
    void modify(un ql,un qr,ll k,un l=1,un r=sam.tot,un num=1)
    {
		if(ql>qr)return;
        if(ql<=l&&r<=qr){rt.sum+=k*(r-l+1),rt.tag+=k;return;}
        pushdown(l,r,num);
        un mid=(l+r)>>1;
        if(ql<=mid)modify(ql,qr,k,l,mid,num<<1);
        if(qr>mid)modify(ql,qr,k,mid+1,r,num<<1|1);
        rt.sum=tl.sum+tr.sum;
    }
    ll Qsum(un ql,un qr,un l=1,un r=sam.tot,un num=1)
    {
		if(ql>qr)return 0;
        if(ql<=l&&r<=qr)return rt.sum;
        pushdown(l,r,num);
        un mid=(l+r)>>1;ll res=0;
        if(ql<=mid)res+=Qsum(ql,qr,l,mid,num<<1);
        if(qr>mid)res+=Qsum(ql,qr,mid+1,r,num<<1|1);
        return res;
    }
    #undef rt
    #undef tl
    #undef tr
}sgt;

struct LCT
{
	int fa[MAXN],son[MAXN][2],tag[MAXN],las[MAXN];
	void init(){for(int i=1;i<=sam.tot;++i)fa[i]=sam.pre[i];}
	bool not_root(int x){return son[fa[x]][0]==x||son[fa[x]][1]==x;}
	void rotate(int x)
	{
		int y=fa[x],z=fa[y],k=(son[y][1]==x);
		if(not_root(y))son[z][son[z][1]==y]=x;
		fa[x]=z;
		son[y][k]=son[x][!k],fa[son[x][!k]]=y;
		son[x][!k]=y,fa[y]=x;
	}
	void pushtag(int x,int val){las[x]=tag[x]=val;}
	void pushdown(int x)
	{
		if(tag[x])pushtag(son[x][0],tag[x]),pushtag(son[x][1],tag[x]),tag[x]=0;
	}
	int s[MAXN];
	void splay(int x)
	{
		int top=0;
		s[++top]=x;
		for(int y=x;not_root(y);y=fa[y])s[++top]=fa[y];
		while(top)pushdown(s[top--]);
		while(not_root(x))
		{
			int y=fa[x];
			if(not_root(y))rotate((son[y][1]==x)==(son[fa[y]][1]==y)?y:x);
			rotate(x);
		}
	}
	void access(int x,int dex)
	{
		int y=0;
		while(x)
		{
			splay(x);
			if(las[x])sgt.modify(las[x]-sam.len[x]+1,las[x]-sam.len[fa[x]],-1);
			son[x][1]=y,y=x,x=fa[x];
		}
		pushtag(y,dex);
		sgt.modify(1,dex,1);
	}
}lct;
std::vector<pii>a[MAXN];
char str[MAXN];
ll ans[MAXN],ed[MAXN];
int main()
{
    scanf("%s",str+1);
    n=strlen(str+1);
    for(int i=1;i<=n;++i)sam.insert(str[i]-'a'),ed[i]=sam.last;
    int m=read();
    for(int i=1;i<=m;++i)
    {
        int l=read(),r=read();a[r].push_back(pii(l,i));
    }
    lct.init();
    for(int i=1;i<=n;++i)
    {
        lct.access(ed[i],i);
        for(std::vector<pii>::iterator it=a[i].begin();it!=a[i].end();++it)
            ans[it->second]=sgt.Qsum(it->first,i);
    }
    for(int i=1;i<=m;++i)printf("%lld\n",ans[i]);
    return 0;
}