建出SAM,考虑离线,每次添加一个前缀节点 $p_i$ 的时候,就是把 $p_i$ 到 $fail$ 树根路径上的节点的最右终止端点改为 $i$ 。
查询 $[L,R]$ 时,只要当前最右终止端点在 $[L,R]$ 范围内的节点都可以计入答案,节点 $x$ 产生的贡献为 $MAX_x-MAX_{fail_x}$ 。
考虑如何维护最右终止端点。我们可以利用LCT,每次 $p_i$ 往上更新其实就是Access操作,每次更新的均摊复杂度是 $O(\log_2n)$ 的。然后利用树状数组查询最右终止端点在 $[L,R]$ 范围内的节点贡献之和。
复杂度是 $O(n\log^2_2n+q\log_2n)$ ,但其实只有Access的LCT+树状数组跑得飞快。
#include<cstdio>
#include<cctype>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
typedef long long LL;
const int maxn=500000,maxt=maxn<<1,maxi=26;
int n,Q,ID[maxn+5];char s[maxn+5];
int pl,ro,fai[maxt+5],son[maxt+5][maxi],MAX[maxt+5],val[maxt+5];
int fa[maxt+5],to[maxt+5][2],pos[maxt+5],tag[maxt+5];LL sum[maxt+5];
pair<pair<int,int>,int> q[maxn+5];
LL ans[maxn+5],c[maxn+5];
#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
static char buf[100000],*l=buf,*r=buf;
return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
T tot=0;char ch=readc(),lst='+';
while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
int reads(char *s){
int len=0;char ch=readc();
while (!islower(ch)) {if (ch==EOF) return EOF;ch=readc();}
while (islower(ch)) s[++len]=ch,ch=readc();
s[len+1]=0;return len;
}
struct fastO{
int si;char buf[100000];
fastO() {si=0;}
void putc(char ch){
if (si==100000) fwrite(buf,1,si,stdout),si=0;
buf[si++]=ch;
}
~fastO() {fwrite(buf,1,si,stdout);}
}fo;
template<typename T> void writei(T x,char ch='\n'){
int len=0,buf[100];
if (x<0) fo.putc('-'),x=-x;
do buf[len++]=x%10,x/=10; while (x);
while (len) fo.putc(buf[--len]+48);
if (ch) fo.putc(ch);
}
inline int newnode() {pl++;return pl;}
int Extend(int p,int c,int id){
int np=newnode();MAX[np]=MAX[p]+1;ID[id]=np;
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;
}
#define is_ro(p) (to[fa[p]][0]!=(p) && to[fa[p]][1]!=(p))
#define Son(p) ((p)==to[fa[p]][1])
inline void Pushup(int p) {sum[p]=sum[to[p][0]]+val[p]+sum[to[p][1]];}
void Rotate(int t){
int p=fa[t],d=Son(t);to[p][d]=to[t][d^1];to[t][d^1]=p;
if (!is_ro(p)) to[fa[p]][Son(p)]=t;Pushup(p);Pushup(t);
if (to[p][d]) fa[to[p][d]]=p;fa[t]=fa[p];fa[p]=t;
}
inline void Addtag(int p,int k) {tag[p]=k;pos[p]=k;}
void Pushdown(int p) {if (tag[p]) Addtag(to[p][0],tag[p]),Addtag(to[p][1],tag[p]),tag[p]=0;}
void Splay(int p){
static int top,stk[maxn+5];stk[top=1]=p;
for (int i=p;!is_ro(i);i=fa[i]) stk[++top]=fa[i];
while (top) Pushdown(stk[top--]);
for (int pre=fa[p];!is_ro(p);Rotate(p),pre=fa[p])
if (!is_ro(pre)) Rotate(Son(p)==Son(pre)?pre:p);
}
void Add(int x,LL y) {for (;x<=n;x+=x&-x) c[x]+=y;}
LL Sum(int x) {int sum=0;for (;x;x-=x&-x) sum+=c[x];return sum;}
void Merge(int p,int j){
for (int lst=0;p;lst=p,p=fa[p]){
Splay(p);
if (pos[p]) Add(pos[p],-sum[to[p][0]]-val[p]);
pos[p]=j;Addtag(to[p][0],j);
Add(j,sum[to[p][0]]+val[p]);
to[p][1]=lst;Pushup(p);
}
}
int main(){
readi(n);readi(Q);reads(s);
ro=newnode();
for (int i=1,p=ro;i<=n;i++) p=Extend(p,s[i]-'a',i);
for (int i=2;i<=pl;i++) fa[i]=fai[i],val[i]=sum[i]=MAX[i]-MAX[fai[i]];
for (int i=1;i<=Q;i++) readi(q[i].fr.sc),readi(q[i].fr.fr),q[i].sc=i;
sort(q+1,q+1+Q);
for (int i=1,j=1;i<=Q;i++){
int L=q[i].fr.sc,R=q[i].fr.fr;
while (j<=n && j<=R) Merge(ID[j],j),j++;
ans[q[i].sc]=Sum(R)-Sum(L-1);
}
for (int i=1;i<=Q;i++) writei(ans[i]);
return 0;
}