题目概述

Cmostp

解题报告

建出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;
}