传送门

不知道是莫队写假了还是人丑常数大,随便一交就是最劣解$QwQ$。

首先来看数据范围:$n^2m\le 10^{15}$

开个方:$n\sqrt{m}\le 3\times 10^7$

这不莫队吗?考虑怎么$O(1)$添加、删除一个后缀的影响。

把串翻转一下就是前缀的最长公共后缀,也就是$SAM$里$parent\ tree$的$LCA$的$len$。

而且某个点子孙的$len$一定大于它自己的$len$。

这样找到所有最高的$len\ge k$的节点,它子树中任意两个节点都能产生$1$贡献。

染个色计数跑一遍莫队就完了。

代码:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

#define maxn 6000005
#define inf 0x3f3f3f3f

using namespace std;

inline int read(){
    int x=0,y=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return y?-x:x;
}
#define son(x,y) son[x][y]
struct Query{
    int l,r,be,num;
    bool operator < (const Query &x)const{
        if(x.be!=be)return be<x.be;
        if(be&1)return r<x.r;
        return r>x.r;
    }
}q[100005];
struct edge{
    int pre,to;
}e[maxn];
int trans[150],son[maxn][7],fa[maxn],len[maxn],c[maxn],top[maxn],h[maxn],w[maxn]={1},num,cnt=1,last=1,k;
long long ans[100005],all;
char s[maxn];
inline void add(int from,int to){
    e[++num].pre=h[from],h[from]=num,e[num].to=to;
}
void dfs(int node=1,int tp=0){
    if(!tp&&len[node]>=k)tp=node;
    top[node]=tp;
    for(register int i=h[node];i;i=e[i].pre)dfs(e[i].to,tp);
}
void insert(int c){
    int p=last,ne=last=++cnt;
    len[ne]=len[p]+1;
    while(p&&!son(p,c))son(p,c)=ne,p=fa[p];
    if(!p)fa[ne]=1;
    else {
        int q=son(p,c);
        if(len[q]==len[p]+1)fa[ne]=q;
        else {
            int sp=++cnt;
            memcpy(son[sp],son[q],sizeof son[q]);
            len[sp]=len[p]+1,fa[sp]=fa[q],fa[q]=fa[ne]=sp;
            while(p&&son(p,c)==q)son(p,c)=sp,p=fa[p];
        }
    }
}
inline void up(int x){
    if(!x)return;
    all+=(c[x]++);
}
inline void down(int x){
    if(!x)return;
    all-=(--c[x]);
}
int main(){
    trans['z']=1,trans['o']=2,trans['u']=3,trans['t']=4,trans['s']=5,trans['y']=6;
    int n=read(),m=read(),sq=n/sqrt(m),l,r;k=read();
    scanf("%s",s+1);
    for(register int i=1;i<=n>>1;++i)swap(s[i]=trans[s[i]],s[n-i+1]=trans[s[n-i+1]]);
    for(register int i=1;i<=n;++i)insert(s[i]);
    for(register int i=1;i<=n;++i)w[i]=son(w[i-1],s[i]);
    for(register int i=2;i<=cnt;++i)add(fa[i],i);
    dfs();
    for(register int i=1;i<=n;++i)w[i]=top[w[i]];
    for(register int i=1;i<=m;++i)l=read(),r=read(),q[i].l=n-r+1,q[i].r=n-l+1,q[i].num=i,q[i].be=l/sq+1;//原串翻转了,询问区间也要翻转
    sort(q+1,q+1+m);
    l=1,r=0;
    for(register int i=1;i<=m;++i){
        while(l<q[i].l)down(w[l++]);
        while(l>q[i].l)up(w[--l]);
        while(r>q[i].r)down(w[r--]);
        while(r<q[i].r)up(w[++r]);
        ans[q[i].num]=all;
    }
    for(register int i=1;i<=m;++i)printf("%lld\n",ans[i]);
}

$P.S$:欢迎$dalao$提出蒟蒻哪里写假了,虽然当最劣解也挺好的