代码

// OFFLINE sweep + single segment tree over compressed tin (max position), L3-resident.
#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 MAXQ 100005
static int *slink, *slen, *sch;
static int stot, n, Q;
static int *head, *nxt, *tin, *tout, *lastpos, *islast, *lastpos_bynode, *node_by_tin;
static int *prefix_last, *rank_of_node, *mn, *mx;
static int *head_r, *nxtq;
static int *mxseg; static int SZ;
static int *tlink, *tlen, *tch, *tval, ttot, *tmx, *tpos;
static int *cnt, *ord;
static int *dstack, *dcur;
static const char **qT; static int *qm, *ql, *qr; static ull *qans;
static inline int imax(int a,int b){return a>b?a:b;}

static inline int seg_exists(int a, int b, int X){
  int l = a + SZ - 1, r = b + SZ - 1;
  while(l <= r){
    if(l & 1){ if(mxseg[l] >= X) return 1; l++; }
    if(!(r & 1)){ if(mxseg[r] >= X) return 1; r--; }
    l >>= 1; r >>= 1;
  }
  return 0;
}
static inline void seg_update(int pos, int val){
  int i = pos + SZ - 1;
  mxseg[i] = val;
  i >>= 1;
  while(i){ int v = mxseg[2*i] > mxseg[2*i+1] ? mxseg[2*i] : mxseg[2*i+1]; if(mxseg[i]==v) break; mxseg[i]=v; i>>=1; }
}

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; islast[cur]=1; lastpos_bynode[cur]=i+1;
  }
}
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; node_by_tin[tin[1]]=1;
  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; node_by_tin[tin[c]]=c; }
    else { tout[u]=timer; top--; }
  }
  int lc=0;
  for(int t=1;t<=stot;t++){ int v=node_by_tin[t]; if(islast[v]){ lc++; rank_of_node[v]=lc; } prefix_last[t]=lc; }
  for(int v=1;v<=stot;v++){ mn[v]=islast[v]?lastpos_bynode[v]:n+1; mx[v]=islast[v]?lastpos_bynode[v]:0; }
  for(int t=stot;t>=2;t--){ int v=node_by_tin[t]; int f=slink[v]; if(mn[v]<mn[f])mn[f]=mn[v]; if(mx[v]>mx[f])mx[f]=mx[v]; }
}
static void solve_query(const char *T, int m, int l, int r, ull *ansp){
  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){ int L=l+now; int ok; if(L<=mn[v] && mx[v]<=r) ok=1; else if(mx[v]<L || mn[v]>r) ok=0; else ok=seg_exists(prefix_last[tin[v]-1]+1, prefix_last[tout[v]], L); if(ok){ 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]; }
  *ansp=ans;
}
int main(void){
  slink=(int*)malloc(sizeof(int)*MAXS); slen=(int*)malloc(sizeof(int)*MAXS); sch=(int*)malloc(sizeof(int)*MAXS*26);
  head=(int*)malloc(sizeof(int)*MAXS); nxt=(int*)malloc(sizeof(int)*MAXS); tin=(int*)malloc(sizeof(int)*MAXS); tout=(int*)malloc(sizeof(int)*MAXS); lastpos=(int*)malloc(sizeof(int)*MAXS);
  islast=(int*)malloc(sizeof(int)*MAXS); lastpos_bynode=(int*)malloc(sizeof(int)*MAXS); node_by_tin=(int*)malloc(sizeof(int)*MAXS);
  prefix_last=(int*)malloc(sizeof(int)*MAXS); rank_of_node=(int*)malloc(sizeof(int)*MAXS); mn=(int*)malloc(sizeof(int)*MAXS); mx=(int*)malloc(sizeof(int)*MAXS);
  head_r=(int*)malloc(sizeof(int)*MAXS); nxtq=(int*)malloc(sizeof(int)*MAXQ);
  tlink=(int*)malloc(sizeof(int)*MAXT); tlen=(int*)malloc(sizeof(int)*MAXT); tch=(int*)malloc(sizeof(int)*MAXT*26); tval=(int*)malloc(sizeof(int)*MAXT); tmx=(int*)malloc(sizeof(int)*MAXT); tpos=(int*)malloc(sizeof(int)*MAXT);
  cnt=(int*)malloc(sizeof(int)*MAXS); ord=(int*)malloc(sizeof(int)*MAXS);
  dstack=(int*)malloc(sizeof(int)*MAXS); dcur=(int*)malloc(sizeof(int)*MAXS);
  qT=(const char**)malloc(sizeof(char*)*MAXQ); qm=(int*)malloc(sizeof(int)*MAXQ); ql=(int*)malloc(sizeof(int)*MAXQ); qr=(int*)malloc(sizeof(int)*MAXQ); qans=(ull*)malloc(sizeof(ull)*MAXQ);
  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[4*1024*1024]; static char local_out[4*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();
  SZ=1; while(SZ<n) SZ<<=1;
  mxseg=(int*)malloc(sizeof(int)*(2*SZ));
  for(int i=0;i<2*SZ;i++) mxseg[i]=0;
  for(int qi=0;qi<Q;qi++){ skip_ws(); qT[qi]=p; while(p<pend && *p>='a'&&*p<='z')++p; qm[qi]=(int)(p-qT[qi]); skip_ws(); ql[qi]=read_int(); skip_ws(); qr[qi]=read_int(); }
  for(int i=1;i<=n;i++) head_r[i]=-1;
  for(int qi=0;qi<Q;qi++){ nxtq[qi]=head_r[qr[qi]]; head_r[qr[qi]]=qi; }
  int prev_r=0;
  for(int r=1;r<=n;r++){
    for(int pp=prev_r+1;pp<=r;pp++) seg_update(rank_of_node[lastpos[pp]], pp);
    prev_r=r;
    for(int qi=head_r[r];qi!=-1;qi=nxtq[qi]){
      if(qi<0) break;
      solve_query(qT[qi], qm[qi], ql[qi], qr[qi], &qans[qi]);
    }
  }
  char *o=obuf;
  for(int qi=0;qi<Q;qi++) o=write_u64(o,qans[qi]);
  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; }
}

评测结果