代码

// v4: binary seg tree with lc/rc interleaved in one array (cache-friendly); iterative query+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 25000000
static int slink[MAXS], slen[MAXS], sch[MAXS*26], sroot[MAXS];
static int stot, n, Q;
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];
#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 int seg_merge(int a, int b) {
  if (!a) return b; if (!b) return a;
  int root = ++sgtot;
  int sa[40], sb[40], sr[40]; 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 la = LC(ca), lb = LC(cb);
    if (la && lb) { int nn=++sgtot; LC(cr)=nn; sa[top]=la; sb[top]=lb; sr[top]=nn; top++; }
    else LC(cr) = la ? la : lb;
    int ra = RC(ca), rb = RC(cb);
    if (ra && rb) { int nn=++sgtot; RC(cr)=nn; sa[top]=ra; sb[top]=rb; sr[top]=nn; top++; }
    else RC(cr) = ra ? ra : rb;
  }
  return root;
}

static inline int seg_query(int u, int L, int R) {
  if (!u || L > R) return 0;
  int stk[24], lo[24], hi[24]; int top=0;
  stk[0]=u; lo[0]=1; hi[0]=n; top=1;
  while (top) {
    top--; int cu=stk[top], cl=lo[top], cr=hi[top];
    if (L<=cl && cr<=R) return 1;
    int mid=(cl+cr)>>1;
    if (R>mid) { int v=RC(cu); if (v) { stk[top]=v; lo[top]=mid+1; hi[top]=cr; top++; } }
    if (L<=mid) { int v=LC(cu); if (v) { stk[top]=v; lo[top]=cl; hi[top]=mid; top++; } }
  }
  return 0;
}

static int seg_newpath(int pos) {
  int root=++sgtot; int u=root; int l=1,r=n;
  while (l<r) { int mid=(l+r)>>1;
    if (pos<=mid) { LC(u)=++sgtot; RC(u)=0; u=LC(u); r=mid; }
    else { RC(u)=++sgtot; LC(u)=0; u=RC(u); l=mid+1; }
  }
  LC(u)=0; RC(u)=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+1);
  }
}
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 && f!=1) 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,r)){ 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; }
}

评测结果