代码

// solution2: chairman tree (persistent segment tree over positions, values = DFS preorder of parent tree)
// No segment-tree merging. Existence query via "uR != uL" trick (2-int nodes).
#include <stdint.h>
#include <sys/auxv.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef unsigned long long ull;
struct DuckInfo {
  uint64_t abi_version; const char *stdin_ptr; uint64_t stdin_size;
  char *stdout_ptr; uint64_t stdout_limit; uint64_t stdout_size;
  char *stderr_ptr; uint64_t stderr_limit; uint64_t stderr_size;
  const char *IB_ptr; uint64_t IB_limit; char *OB_ptr; uint64_t OB_limit; uint64_t tsc_frequency;
} __attribute__((packed));
#define MAXS 1000005
#define MAXT 2000005
#define MAXSEG 11500000
static int slink[MAXS], slen[MAXS], sch[MAXS*26];
static int stot, n, Q;
static int head[MAXS], nxt[MAXS], tin[MAXS], tout[MAXS], lastpos[MAXS];
static int root[MAXS];
static int seg[MAXSEG*2];
static int sgtot;
static int tlink[MAXT], tlen[MAXT], tch[MAXT*26], tval[MAXT], ttot, tmx[MAXT], tpos[MAXT];
static int cnt[MAXS], ord[MAXS];
static int dstack[MAXS], dcur[MAXS];
#define LC(u) seg[((u)<<1)]
#define RC(u) seg[(((u)<<1)|1)]
static inline int imax(int a,int b){return a>b?a:b;}

static inline int pst_insert(int prev, int val){
  int rroot = ++sgtot;
  LC(rroot)=LC(prev); RC(rroot)=RC(prev);
  int u = rroot, p = prev;
  int lo=1, hi=stot;
  while(lo<hi){
    int mid=(lo+hi)>>1;
    if(val<=mid){
      int nn=++sgtot;
      int old=LC(p);
      LC(nn)=LC(old); RC(nn)=RC(old);
      LC(u)=nn;
      u=nn; p=old; hi=mid;
    } else {
      int nn=++sgtot;
      int old=RC(p);
      LC(nn)=LC(old); RC(nn)=RC(old);
      RC(u)=nn;
      u=nn; p=old; lo=mid+1;
    }
  }
  return rroot;
}

// any point among positions [L,R] with value (tin) in [a,b]
static inline int pst_exists(int uR, int uL, int a, int b){
  if(uR==uL) return 0;
  int qR[24], qL[24], qlo[24], qhi[24]; int top=0;
  qR[0]=uR; qL[0]=uL; qlo[0]=1; qhi[0]=stot; top=1;
  while(top){
    top--;
    int ur=qR[top], ul=qL[top], lo=qlo[top], hi=qhi[top];
    if(a<=lo && hi<=b) return 1;
    int mid=(lo+hi)>>1;
    if(b<=mid){
      int nr=LC(ur), nl=LC(ul);
      if(nr!=nl){ qR[top]=nr; qL[top]=nl; qlo[top]=lo; qhi[top]=mid; top++; }
    } else if(a>mid){
      int nr=RC(ur), nl=RC(ul);
      if(nr!=nl){ qR[top]=nr; qL[top]=nl; qlo[top]=mid+1; qhi[top]=hi; top++; }
    } else {
      int rr=RC(ur), rl=RC(ul);
      if(rr!=rl){ qR[top]=rr; qL[top]=rl; qlo[top]=mid+1; qhi[top]=hi; top++; }
      int lr=LC(ur), ll=LC(ul);
      if(lr!=ll){ qR[top]=lr; qL[top]=ll; qlo[top]=lo; qhi[top]=mid; top++; }
    }
  }
  return 0;
}

static const char *p, *pend;
static inline void skip_ws(void){ while(p<pend && (*p==' '||*p=='\n'||*p=='\r'||*p=='\t')) ++p; }
static inline int read_int(void){ int x=0; while(p<pend && *p>='0'&&*p<='9'){x=x*10+(*p-'0');++p;} return x; }
static inline char *write_u64(char *o, ull x){ if(x==0){*o++='0';*o++='\n';return o;} char tmp[24]; int t=0; while(x){tmp[t++]=(char)('0'+(int)(x%10));x/=10;} while(t)*o++=tmp[--t]; *o++='\n'; return o; }

static void build_S_sam(const char *S){
  stot=1; slen[1]=0; slink[1]=0; memset(sch+26,0,26*sizeof(int)); int last=1;
  for(int i=0;i<n;i++){ int c=S[i]-'a'; int cur=++stot; slen[cur]=slen[last]+1; slink[cur]=0; memset(sch+cur*26,0,26*sizeof(int));
    int pp=last; while(pp && sch[pp*26+c]==0){ sch[pp*26+c]=cur; pp=slink[pp]; }
    if(!pp) slink[cur]=1; else { int q=sch[pp*26+c]; if(slen[pp]+1==slen[q]) slink[cur]=q; else { int cl=++stot; slen[cl]=slen[pp]+1; slink[cl]=slink[q]; memcpy(sch+cl*26,sch+q*26,26*sizeof(int)); while(pp && sch[pp*26+c]==q){ sch[pp*26+c]=cl; pp=slink[pp];} slink[q]=slink[cur]=cl; } }
    last=cur; lastpos[i+1]=cur;
  }
}

static void build_parent_tree(void){
  for(int v=1;v<=stot;v++) head[v]=0;
  for(int v=2;v<=stot;v++){ nxt[v]=head[slink[v]]; head[slink[v]]=v; }
  int top=0, timer=0;
  dstack[0]=1; dcur[0]=head[1]; top=1; tin[1]=++timer;
  while(top){
    int u=dstack[top-1];
    int c=dcur[top-1];
    if(c){ dcur[top-1]=nxt[c]; dstack[top]=c; dcur[top]=head[c]; top++; tin[c]=++timer; }
    else { tout[u]=timer; top--; }
  }
}

static void build_chairman(void){
  sgtot=0; root[0]=0;
  for(int pp=1;pp<=n;pp++) root[pp]=pst_insert(root[pp-1], tin[lastpos[pp]]);
}

static void solve_query(const char *T, int m, int l, int r, char **optr){
  char *o=*optr;
  ttot=1; tlen[1]=0; tlink[1]=0; tval[1]=0; memset(tch+26,0,26*sizeof(int)); int last=1;
  for(int i=1;i<=m;i++){ int c=T[i-1]-'a'; int cur=++ttot; tlen[cur]=tlen[last]+1; tlink[cur]=0; tval[cur]=0; memset(tch+cur*26,0,26*sizeof(int));
    int pp=last; while(pp && tch[pp*26+c]==0){ tch[pp*26+c]=cur; pp=tlink[pp]; }
    if(!pp) tlink[cur]=1; else { int q=tch[pp*26+c]; if(tlen[pp]+1==tlen[q]) tlink[cur]=q; else { int cl=++ttot; tlen[cl]=tlen[pp]+1; tlink[cl]=tlink[q]; tval[cl]=0; memcpy(tch+cl*26,tch+q*26,26*sizeof(int)); while(pp && tch[pp*26+c]==q){ tch[pp*26+c]=cl; pp=tlink[pp];} tlink[q]=tlink[cur]=cl; } }
    last=cur; tpos[i]=cur;
  }
  int u=1, now=0;
  int rr=root[r];
  for(int i=1;i<=m;i++){ int c=T[i-1]-'a';
    for(;;){ int v=sch[u*26+c]; if(v && (l+now)<=r && pst_exists(rr, root[l+now-1], tin[v], tout[v])){ u=v; now++; break; } if(now==0) break; now--; if(now==slen[slink[u]]) u=slink[u]; }
    tmx[i]=now;
  }
  for(int i=1;i<=m;i++) tval[tpos[i]]=tmx[i];
  memset(cnt,0,(size_t)(m+1)*sizeof(int)); for(int v=1;v<=ttot;v++)cnt[tlen[v]]++; for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1]; for(int v=1;v<=ttot;v++)ord[--cnt[tlen[v]]]=v;
  ull ans=0;
  for(int i=ttot-1;i>=1;i--){ int v=ord[i]; int x=tlen[v]-imax(tlen[tlink[v]],tval[v]); if(x>0)ans+=(ull)x; int f=tlink[v]; if(tval[v]>tval[f])tval[f]=tval[v]; }
  o=write_u64(o,ans); *optr=o;
}

int main(void){
  struct DuckInfo *di=(struct DuckInfo*)getauxval(0x6b637564);
  const char *inp; size_t inlen; char *obuf; size_t ocap; int is_judge=0;
  static char local_in[64*1024*1024]; static char local_out[16*1024*1024];
  if(di && di->stdin_ptr && di->stdin_size){ inp=di->stdin_ptr; inlen=(size_t)di->stdin_size; obuf=di->stdout_ptr; ocap=(size_t)di->stdout_limit; is_judge=1; }
  else { inlen=fread(local_in,1,sizeof(local_in),stdin); inp=local_in; obuf=local_out; ocap=sizeof(local_out); }
  p=inp; pend=inp+inlen;
  skip_ws(); const char *S=p; while(p<pend && *p>='a'&&*p<='z')++p; n=(int)(p-S); skip_ws(); Q=read_int();
  build_S_sam(S); build_parent_tree(); build_chairman();
  char *o=obuf;
  for(int qi=0;qi<Q;qi++){ skip_ws(); const char *T=p; while(p<pend && *p>='a'&&*p<='z')++p; int m=(int)(p-T); skip_ws(); int l=read_int(); skip_ws(); int r=read_int(); solve_query(T,m,l,r,&o); }
  size_t osize=(size_t)(o-obuf);
  if(is_judge){ di->stdout_size=osize; asm volatile("mov $60, %%eax; xor %%edi, %%edi; syscall" ::: "rax","rdi","memory"); __builtin_unreachable(); }
  else { fwrite(obuf,1,osize,stdout); return 0; }
}

评测结果