代码

// v8: hybrid endpos representation: single-position nodes use mn/mx (no tree); multi-position nodes use a
// persistent binary segment tree built by insert + merge.  Iterative query/merge/insert.
#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 12000000
static int slink[MAXS], slen[MAXS], sch[MAXS*26], sroot[MAXS];
static int mnS[MAXS], mxS[MAXS];
static int stot, n, Q;
static int LC[MAXSEG], RC[MAXSEG];
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[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;
}

// persistent insert of position pos into tree rooted at root
static int seg_insert(int root, int pos) {
  int newroot = ++sgtot;
  int cu = newroot, old = root;
  int l = 1, r = n;
  while (l < r) {
    int mid = (l + r) >> 1;
    if (pos <= mid) {
      LC[cu] = ++sgtot;
      RC[cu] = RC[old];
      old = LC[old];
      cu = LC[cu];
      r = mid;
    } else {
      RC[cu] = ++sgtot;
      LC[cu] = LC[old];
      old = RC[old];
      cu = RC[cu];
      l = mid + 1;
    }
  }
  LC[cu] = 0; RC[cu] = 0;
  return newroot;
}

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 inline int has_endpos(int v, int L, int R) {
  if (mxS[v] < L || mnS[v] > R) return 0;
  if (mnS[v] == mxS[v]) return 1;
  return seg_query(sroot[v], L, R);
}

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; mnS[1]=n+1; mxS[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; mnS[cur]=i+1; mxS[cur]=i+1; 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; mnS[cl]=n+1; mxS[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;
  }
}
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 (sroot[v] == 0) {
      // v single endpos (mnS[v]==mxS[v])
      int pp = mnS[v];
      if (mxS[f] == 0) { mnS[f]=pp; mxS[f]=pp; }
      else if (mnS[f] == mxS[f]) { int q=mnS[f]; sroot[f]=seg_insert(0,q); sroot[f]=seg_insert(sroot[f],pp); if(pp<mnS[f])mnS[f]=pp; else mxS[f]=pp; }
      else { sroot[f]=seg_insert(sroot[f],pp); if(pp<mnS[f])mnS[f]=pp; if(pp>mxS[f])mxS[f]=pp; }
    } else {
      if (mxS[f] == 0) { sroot[f]=sroot[v]; mnS[f]=mnS[v]; mxS[f]=mxS[v]; }
      else if (mnS[f] == mxS[f]) { sroot[f]=seg_insert(sroot[v], mnS[f]); if(mnS[v]<mnS[f])mnS[f]=mnS[v]; if(mxS[v]>mxS[f])mxS[f]=mxS[v]; }
      else { sroot[f]=seg_merge(sroot[f],sroot[v]); if(mnS[v]<mnS[f])mnS[f]=mnS[v]; if(mxS[v]>mxS[f])mxS[f]=mxS[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 && has_endpos(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; }
}

评测结果