代码

// v10: 8-way segment tree, bit-shift query (no division), iterative merge.
#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 9000000
#define LEV 7
#define UNIV 2097152
static int slink[MAXS], slen[MAXS], sch[MAXS*26], sroot[MAXS];
static int stot, n, Q;
static int ch8[MAXSEG*8];
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 inline int imax(int a,int b){return a>b?a:b;}

static int seg_merge(int a, int b) {
  if (!a) return b; if (!b) return a;
  int root = ++sgtot;
  int sa[128], sb[128], sr[128]; int top=0;
  sa[0]=a; sb[0]=b; sr[0]=root; top=1;
  while (top) {
    top--; int ca=sa[top], cb=sb[top], cr=sr[top];
    int *pa = ch8 + ca*8, *pb = ch8 + cb*8, *pc = ch8 + cr*8;
    for (int j=0; j<8; j++) {
      int xa = pa[j], xb = pb[j];
      if (xa && xb) { int nn=++sgtot; pc[j]=nn; sa[top]=xa; sb[top]=xb; sr[top]=nn; top++; }
      else pc[j] = xa ? xa : xb;
    }
  }
  return root;
}

static inline int seg_query(int u, int L, int R) {
  if (!u || L > R) return 0;
  int stk[64], lo[64], sh[64]; int top=0;
  stk[0]=u; lo[0]=0; sh[0]=18; top=1;
  while (top) {
    top--; int cu=stk[top], cl=lo[top], cs=sh[top];
    int cr = cl + (1 << (cs+3)) - 1;
    if (L <= cl && cr <= R) return 1;
    if (cs < 0) continue;
    int block = 1 << cs;
    int j1 = (L - cl) >> cs;
    int j2 = (R - cl) >> cs;
    if (j1 < 0) j1 = 0;
    if (j2 > 7) j2 = 7;
    int *pc = ch8 + cu*8;
    int ns = cs - 3;
    for (int j = j2; j >= j1; j--) {
      int v = pc[j];
      if (v) { stk[top]=v; lo[top]=cl + (j << cs); sh[top]=ns; top++; }
    }
  }
  return 0;
}

static int seg_newpath(int pos) {
  int root=++sgtot; int u=root;
  for (int k=0;k<LEV;k++){ int shift=3*(LEV-1-k); int j=(pos>>shift)&7;
    int *pc=ch8+u*8; for(int c=0;c<8;c++) pc[c]=0; pc[j]=++sgtot; u=pc[j]; }
  int *pc=ch8+u*8; for(int c=0;c<8;c++) pc[c]=0;
  return root;
}

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; sroot[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; sroot[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]; sroot[cl]=0; 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; sroot[cur]=seg_newpath(i);
  }
}
static void build_endpos(void){
  memset(cnt,0,(size_t)(n+1)*sizeof(int)); for(int v=1;v<=stot;v++)cnt[slen[v]]++; for(int i=1;i<=n;i++)cnt[i]+=cnt[i-1]; for(int v=1;v<=stot;v++)ord[--cnt[slen[v]]]=v;
  for(int i=stot-1;i>=1;i--){ int v=ord[i]; int f=slink[v]; if(f) sroot[f]=seg_merge(sroot[f],sroot[v]); }
}
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;
  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 && seg_query(sroot[v],l+now-1,r-1)){ 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_endpos();
  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; }
}

评测结果