代码

// v2: iterative seg_query + iterative seg_merge (binary tree), else same as solution.cpp
#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];
static int slen[MAXS];
static int sch[MAXS * 26];
static int sroot[MAXS];
static int stot, n, Q;

static int slc[MAXSEG];
static int src[MAXSEG];
static int sgtot;

static int tlink[MAXT];
static int tlen[MAXT];
static int tch[MAXT * 26];
static int tval[MAXT];
static int ttot;
static int tmx[MAXT];
static int tpos[MAXT];

static int cnt[MAXS];
static int ord[MAXS];

static inline int imax(int a, int b) { return a > b ? a : b; }

// iterative persistent merge
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 = slc[ca], lb = slc[cb];
    if (la && lb) { int nn = ++sgtot; slc[cr] = nn; sa[top] = la; sb[top] = lb; sr[top] = nn; top++; }
    else slc[cr] = la ? la : lb;
    int ra = src[ca], rb = src[cb];
    if (ra && rb) { int nn = ++sgtot; src[cr] = nn; sa[top] = ra; sb[top] = rb; sr[top] = nn; top++; }
    else src[cr] = ra ? ra : rb;
  }
  return root;
}

// iterative query: any endpos in [L, R]
static inline int seg_query(int u, int L, int R) {
  if (!u) 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 = src[cu]; if (v) { stk[top] = v; lo[top] = mid + 1; hi[top] = cr; top++; } }
    if (L <= mid) { int v = slc[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) { slc[u] = ++sgtot; src[u] = 0; u = slc[u]; r = mid; }
    else { src[u] = ++sgtot; slc[u] = 0; u = src[u]; l = mid + 1; }
  }
  slc[u] = 0; src[u] = 0;
  return root;
}

static const char *p;
static const char *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) 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;
  }
}

评测结果