题解 P6292 【【模板】区间本质不同子串个数】

对于每个本质不同的字符串 T，假设在前缀 [1,r] 中最后一次出现的位置（右端点）为 last_T，那么当左端点取到 [1,last_T-|T|+1] 这个区间内的时候，T 会对答案产生 1 的贡献。

采用扫描线的思路，对每个右端点维护所有左端点的答案。

如果把反串的后缀树建出来，那么将右端点右移一位到达 r 就相当于将后缀树上一条到根的路径上的所有字符串的 last 修改成 r。如果把这个看作 LCT 中的 access 操作，可以发现划分出来的每条链上的 last 都相同，并且代表的字符串长度连续。

因此直接用 LCT 进行修改，将链合并的时候就是将一段长度连续的本质不同字符串的 last 进行修改，这个对答案的影响可以表现成区间加一个公差为 1 的等差数列，用线段树维护即可。

注意到 access 操作的次数是均摊 O(logn)，那么只会进行 O(nlogn) 次线段树上的区间修改，复杂度是 O(nlog^2n) 的。而线段树上查询一次的复杂度是 O(logn)，所以总复杂度是 O(nlog^2n+mlogn)。

我的实现中将区间加等差数列单点查询转化成区间加常数区间查询，用树状数组实现的时候感觉稍微好写一些。

#include<bits/stdc++.h>
using namespace std;
#define I inline int
#define V inline void
#define P pair<int,int>
#define ll long long int
#define FOR(i,a,b) for(int i=a;i<=b;i++)
const int N=2e5+1,INF=0x3f3f3f3f;
V cmin(int&x,int y){if(y-x>>31)x=y;}
namespace SAM{
    int ch[N][26],fa[N],len[N],tot=1,last=1;
    V cpy(int x,int y){FOR(i,0,25)ch[x][i]=ch[y][i];}
    I ins(int x){
        int p(last),np,q,nq;
        len[np=last=++tot]=len[p]+1;
        while(p&&!ch[p][x])ch[p][x]=np,p=fa[p];
        if(!p)return fa[np]=1,last;
        if(len[q=ch[p][x]]==len[p]+1)return fa[np]=q,last;
        cpy(nq=++tot,q),len[nq]=len[p]+1,fa[nq]=fa[q],fa[q]=fa[np]=nq;
        while(p&&ch[p][x]==q)ch[p][x]=nq,p=fa[p];
        return last;
    }
}
namespace seg{
    ll c[N],d[N];
    I lowbit(int x){return x&-x;}
    V add(int x,int y){for(ll w=x*y;x<N;x+=lowbit(x))c[x]+=y,d[x]+=w;}
    ll ask(int x){
        ll out=0,tmp=0;
        for(int p=x;p;p^=lowbit(p))out+=c[p],tmp+=d[p];
        return out*(x+1)-tmp;
    }
    ll ask(int l,int r){return ask(r)-ask(l-1);}
    V add(int l,int r,int x){add(l,x),add(r+1,-x);}
}
namespace LCT{
    int fa[N],ch[N][2],last[N],tag[N],len[N],val[N];
    I id(int x){return x==ch[fa[x]][1];}
    I nrt(int x){return x==ch[fa[x]][id(x)];}
    V upd(int x){val[x]=len[x];FOR(i,0,1)cmin(val[x],val[ch[x][i]]);}
    V rot(int x){
        int y=fa[x],z=fa[y],p=id(x),w=ch[x][p^1];
        if(nrt(y))ch[z][id(y)]=x;if(w)fa[w]=y;
        fa[y]=x,fa[x]=z,ch[x][p^1]=y,ch[y][p]=w,upd(y),upd(x);
    }
    V add(int x,int w){last[x]=tag[x]=w;}
    V psd(int x){if(tag[x])FOR(i,0,1)add(ch[x][i],tag[x]);tag[x]=0;}
    V psa(int x){if(nrt(x))psa(fa[x]);psd(x);}
    V spl(int x){
        for(psa(x);nrt(x);rot(x))if(nrt(fa[x]))
            rot(id(x)==id(fa[x])?fa[x]:x);
    }
    V acc(int x,int now){
        for(int p=x,y=0;p;p=fa[y=p]){
            spl(p),ch[p][1]=y,upd(p);
            if(last[p])seg::add(last[p]-SAM::len[p]+1,last[p]-val[p]+1,-1);
        }
        spl(x),add(x,now),seg::add(now-SAM::len[x]+1,now,1);
    }
    V init(){
        val[0]=INF;
        FOR(i,1,SAM::tot){
            val[i]=len[i]=SAM::len[fa[i]=SAM::fa[i]]+1;
            tag[i]=ch[i][0]=ch[i][1]=last[i]=0;
        }
    }
}
char a[N];
ll ans[N];
vector<P>q[N];
int T,n,m,l,r,pos[N];
int main(){
    scanf("%s%d",a+1,&m),n=strlen(a+1);
    FOR(i,1,m)scanf("%d%d",&l,&r),q[r].push_back(P(i,l));
    FOR(i,1,n)pos[i]=SAM::ins(a[i]-'a');
    LCT::init();
    FOR(i,1,n){
        LCT::acc(pos[i],i);
        for(P x:q[i])ans[x.first]=seg::ask(x.second,i);
    }
    FOR(i,1,m)cout<<ans[i]<<'\n';
    return 0;
}