代码

// NOI2018 你的名字 (duck.ac noi18c)
// Standard solution: SAM of S + persistent segment tree merge for endpos.
// Per query: build T's SAM, match T against S[l..r] using the segment tree,
// then answer = sum over T-SAM nodes max(0, len[v] - max(len[link[v]], maxMatch[v])).
#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       // <= 2*|S| + 2
#define MAXT 2000005       // <= 2*|T| + 2
#define MAXSEG 25000000    // persistent seg-tree merge: O(|S| log |S|)

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; }

// persistent merge of two endpos segment trees (creates new nodes; safe to share)
static int seg_merge(int a, int b) {
  if (!a) return b;
  if (!b) return a;
  int cur = ++sgtot;
  slc[cur] = seg_merge(slc[a], slc[b]);
  src[cur] = seg_merge(src[a], src[b]);
  return cur;
}

// does the segment tree rooted at u contain any endpos in [L, R] (1..n)?
static int seg_query(int u, int L, int R, int l, int r) {
  if (!u) return 0;
  if (L <= l && r <= R) return 1;
  int mid = (l + r) >> 1;
  if (L <= mid && seg_query(slc[u], L, R, l, mid)) return 1;
  if (R > mid && seg_query(src[u], L, R, mid + 1, r)) return 1;
  return 0;
}

// build a fresh leaf path to position pos (1-indexed); returns root
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;
  memset(sch + 26, 0, 26 * sizeof(int));
  sroot[1] = 0;
  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) {
  // counting sort nodes by len (ascending)
  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;
  // process descending len: merge child segment trees into parents
  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;
  // build T SAM
  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;
  }
  // match T against S[l..r]
  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, 1, n)) {
        u = v;
        now++;
        break;
      }
      if (now == 0) break;
      now--;
      if (now == slen[slink[u]]) u = slink[u];
    }
    tmx[i] = now;
  }
  // tree DP: maxMatch per node, then answer
  for (int i = 1; i <= m; i++) tval[tpos[i]] = tmx[i];
  // counting sort T nodes by len ascending
  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;
  char *oend = obuf + ocap;
  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);
    (void)oend;
  }

  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;
  }
}

评测结果