代码

// This code is AI-generated. (AI 生成的代码)
// NOI2018 你的名字.
// Build the suffix automaton of S.  For a fixed right end r, sweep positions
// into a segment tree keyed by the "last prefix" order of the parent tree, so
// for a query [l,r] a SAM state v "occurs in S[l..r]" iff its parent-tree tin
// interval contains a prefix position >= l+|match|-1.  Each query builds the SAM
// of T, matches T against S's SAM while clamping the match to the range, then
// subtracts the distinct substrings of T that occur in S[l..r].
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <sys/auxv.h>
#include <cstdio>

typedef unsigned long long ull;

struct DuckInfo {
    uint64_t abi; 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;
} __attribute__((packed));

enum { MAXS = 1000005, MAXT = 2000005, MAXQ = 100005 };

static int *slink, *slen, *sch;
static int stot;
static int *head, *nxt, *tin, *tout, *lastpos, *islast, *pos_of_node, *node_by_tin;
static int *pref_last, *rank_of_node, *mn, *mx;
static int *head_r, *nxtq;
static int *mxseg, SZ;
static int *tlink, *tlen, *tch, *tval, *tmx, *tpos;
static int *cnt, *ord, *dstack, *dcur;
static const char **qT;
static int *qm, *ql, *qr;
static ull *qans;
static int n, Q;
static const char *ip, *ipend;

static inline void skip_ws() { while (ip < ipend && (*ip <= ' ')) ++ip; }
static inline int read_int() { int x = 0; while (ip < ipend && *ip >= '0' && *ip <= '9') x = x * 10 + (*ip++ - '0'); return x; }
static inline char *write_u64(char *o, ull x) {
    if (!x) { *o++ = '0'; *o++ = '\n'; return o; }
    char t[24]; int k = 0;
    while (x) { t[k++] = (char)('0' + x % 10); x /= 10; }
    while (k) *o++ = t[--k];
    *o++ = '\n';
    return o;
}
static inline int imax(int a, int b) { return a > b ? a : b; }

static void build_sam_s(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; pos_of_node[cur] = i + 1;
    }
}

static void build_parent_tree() {
    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[timer] = 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[timer] = 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]) rank_of_node[v] = ++lc; pref_last[t] = lc; }
    for (int v = 1; v <= stot; ++v) { mn[v] = islast[v] ? pos_of_node[v] : n + 1; mx[v] = islast[v] ? pos_of_node[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 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 void solve_query(const char *T, int m, int l, int r, ull *ansp) {
    int 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, ok;
                if (L <= mn[v] && mx[v] <= r) ok = 1;
                else if (mx[v] < L || mn[v] > r) ok = 0;
                else ok = seg_exists(pref_last[tin[v] - 1] + 1, pref_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() {
    slink = (int *)malloc(sizeof(int) * MAXS); slen = (int *)malloc(sizeof(int) * MAXS);
    sch = (int *)malloc(sizeof(int) * (size_t)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);
    pos_of_node = (int *)malloc(sizeof(int) * MAXS); node_by_tin = (int *)malloc(sizeof(int) * MAXS);
    pref_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) * (size_t)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(0x6b637564UL);
    char *obuf;
    int is_judge = 0;
    static char local_in[1 << 25], local_out[1 << 26];
    if (di && di->stdin_ptr && di->stdin_size) {
        ip = di->stdin_ptr; ipend = ip + di->stdin_size; obuf = di->stdout_ptr; is_judge = 1;
    } else {
        size_t z = fread(local_in, 1, sizeof(local_in), stdin);
        ip = local_in; ipend = ip + z; obuf = local_out;
    }
    skip_ws();
    const char *S = ip;
    while (ip < ipend && *ip >= 'a' && *ip <= 'z') ++ip;
    n = (int)(ip - S);
    skip_ws(); Q = read_int();
    build_sam_s(S);
    build_parent_tree();
    SZ = 1; while (SZ < n) SZ <<= 1;
    mxseg = (int *)malloc(sizeof(int) * (2 * SZ));
    memset(mxseg, 0, sizeof(int) * (2 * SZ));
    for (int qi = 0; qi < Q; ++qi) {
        skip_ws(); qT[qi] = ip;
        while (ip < ipend && *ip >= 'a' && *ip <= 'z') ++ip;
        qm[qi] = (int)(ip - 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();
    }
#ifdef LOCAL
    fwrite(obuf, 1, osize, stdout);
#endif
    return 0;
}

评测结果