题目概述

HydroH1079

解题报告

建出SAM，找到 $[A,B]$ 对应节点 $p$ ，然后在 $p$ 的 $Right$ 集合上考虑。

$[C,D]$ 中出现 $[A,B]$ 的子串比较难算，考虑算不合法的子串。

令 $len=B-A+1$ ，则 $<len$ 的子串显然是不满足的，然后考虑 $\ge len$ 的不满足子串，假设区间为 $[L,R]$ ，则 $[L+len-1,R]$ 这些部分不能出现 $[A,B]$ 的 $Right$ 集合（设为 $\{pos\}$ ），也就是说 $pos_k,pos_{k+1}$ 之间的 $[L+len-1,R]$ 都是不满足的，个数为：

$$ \sum_{k}\sum_{i=1}^{pos_{k+1}-pos_k-1}i $$

由于统计的是 $[L+len-1,R]$ ，所以 $\{pos\}$ 查询的是 $[C+len-1,D]$ 的部分，可以用线段树合并处理。

示例程序

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=200000,maxs=maxn<<1,maxi=26,LOG=18,maxt=1e7;

int te,n,pos[maxn+5];char s[maxn+5];
vector<int> e[maxs+5];
struct SAM{
    int pl,ro,son[maxs+5][maxi],fai[maxs+5],MAX[maxs+5],ID[maxs+5];
    inline int newnode() {pl++;return pl;}
    SAM() {pl=0;ro=newnode();}
    int Extend(int p,int c,int i){
        int np=newnode();MAX[np]=MAX[p]+1;ID[np]=i;
        while (p && !son[p][c]) son[p][c]=np,p=fai[p];
        if (!p) {fai[np]=ro;return np;}
        int q=son[p][c];if (MAX[p]+1==MAX[q]) {fai[np]=q;return np;}
        int nq=newnode();MAX[nq]=MAX[p]+1;
        for (int i=0;i<maxi;i++) son[nq][i]=son[q][i];
        fai[nq]=fai[q];fai[q]=fai[np]=nq;
        while (p && son[p][c]==q) son[p][c]=nq,p=fai[p];
        return np;
    }
    void Make() {for (int i=2;i<=pl;i++) e[fai[i]].push_back(i);}
}SAM;
int ST[LOG+1][maxs+5];
int pl,ro[maxs+5],ls[maxt+5],rs[maxt+5];
struct DATA {int pre,suf;LL sum;} val[maxt+5];

inline int newnode() {pl++;return pl;}
LL Sum(LL L,LL R) {return L<=R?(L+R)*(R-L+1)/2:0;}
DATA Merge(const DATA &a,const DATA &b){
    static DATA c;
    c.sum=a.sum+b.sum;
    if (a.suf && b.pre) c.sum+=Sum(1,b.pre-a.suf-1);
    c.pre=(a.pre?a.pre:b.pre);
    c.suf=(b.suf?b.suf:a.suf);
    return c;
}
int Insert(int p,int pos,int l=1,int r=n){
    int now=newnode();
    ls[now]=ls[p];rs[now]=rs[p];
    if (l==r) {val[now]=DATA{l,l,0};return now;}
    int mid=l+(r-l>>1);
    pos<=mid?ls[now]=Insert(ls[p],pos,l,mid):rs[now]=Insert(rs[p],pos,mid+1,r);
    val[now]=Merge(val[ls[now]],val[rs[now]]);
    return now;
}
int Merge(int x,int y){
    if (!x && !y) return 0;
    int now=newnode();
    if (!x || !y){
        ls[now]=ls[x+y];rs[now]=rs[x+y];val[now]=val[x+y];
        return now;
    }
    ls[now]=Merge(ls[x],ls[y]);
    rs[now]=Merge(rs[x],rs[y]);
    val[now]=Merge(val[ls[now]],val[rs[now]]);
    return now;
}
void DFS(int x,int pre=0){
    ST[0][x]=pre;
    for (int j=1;j<=LOG;j++) ST[j][x]=ST[j-1][ST[j-1][x]];
    if (SAM.ID[x]) ro[x]=Insert(ro[x],SAM.ID[x]);
    for (auto u:e[x]) DFS(u,x),ro[x]=Merge(ro[x],ro[u]);
}
int Findp(int L,int R){
    int x=pos[R];
    for (int j=LOG;~j;j--)
        if (SAM.MAX[ST[j][x]]>=R-L+1) x=ST[j][x];
    return x;
}
DATA Ask(int p,int L,int R,int l=1,int r=n){
    if (!p) return DATA{0,0,0};
    if (L==l && r==R) return val[p];
    int mid=l+(r-l>>1);
    if (R<=mid) return Ask(ls[p],L,R,l,mid); else if (L>mid) return Ask(rs[p],L,R,mid+1,r);
    else return Merge(Ask(ls[p],L,mid,l,mid),Ask(rs[p],mid+1,R,mid+1,r));
}
int main(){
    scanf("%s",s+1);n=strlen(s+1);
    for (int i=1,p=SAM.ro;i<=n;i++) pos[i]=p=SAM.Extend(p,s[i]-'a',i);
    SAM.Make();DFS(SAM.ro);
    for (scanf("%d",&te);te;te--){
        int A,B,C,D;
        scanf("%d%d%d%d",&A,&B,&C,&D);
        int len=B-A+1,tot=D-C+1;
        if (len>tot) {puts("0");continue;}
        int p=Findp(A,B);
        LL ans=Sum(1,tot)-Sum(tot-(len-1)+1,tot);
        DATA res=Ask(ro[p],C+len-1,D);
        ans-=res.sum;
        if (res.pre) ans-=Sum(1,res.pre-(C+len-1)),ans-=Sum(1,D-res.suf);
        else ans-=Sum(1,D-(C+len-1)+1);
        printf("%lld\n",ans);
    }
    return 0;
}