代码

#ifndef DUCK_FASTIO_H
#define DUCK_FASTIO_H

typedef unsigned long duck_u64;
typedef long duck_i64;

typedef struct {
    duck_u64 abi_version;
    const char *stdin_ptr;
    duck_u64 stdin_size;
    char *stdout_ptr;
    duck_u64 stdout_limit;
    duck_u64 stdout_size;
    char *stderr_ptr;
    duck_u64 stderr_limit;
    duck_u64 stderr_size;
    const char *ib_ptr;
    duck_u64 ib_limit;
    char *ob_ptr;
    duck_u64 ob_limit;
    duck_u64 tsc_frequency;
} __attribute__((packed)) DuckInfo;

static __attribute__((always_inline)) inline DuckInfo *duck_info(long argc, char **argv) {
    char **p = argv + argc + 1;
    while (*p) ++p;
    duck_u64 *aux = (duck_u64 *)(p + 1);
    while (aux[0]) {
        if (aux[0] == 0x6b637564UL) return (DuckInfo *)aux[1];
        aux += 2;
    }
    return (DuckInfo *)0;
}

static __attribute__((always_inline)) inline duck_u64 duck_read_u64(const char **cursor) {
    const char *p = *cursor;
    while ((unsigned char)(*p - '0') > 9) ++p;
    duck_u64 value = 0;
    do {
        value = value * 10 + (unsigned char)(*p - '0');
        ++p;
    } while ((unsigned char)(*p - '0') <= 9);
    *cursor = p;
    return value;
}

static __attribute__((always_inline)) inline duck_i64 duck_read_i64(const char **cursor) {
    const char *p = *cursor;
    while (*p != '-' && (unsigned char)(*p - '0') > 9) ++p;
    int negative = *p == '-';
    p += negative;
    duck_u64 value = 0;
    do {
        value = value * 10 + (unsigned char)(*p - '0');
        ++p;
    } while ((unsigned char)(*p - '0') <= 9);
    *cursor = p;
    return negative ? -(duck_i64)value : (duck_i64)value;
}

static __attribute__((always_inline)) inline char *duck_write_u64(char *out, duck_u64 value) {
    char tmp[24];
    unsigned n = 0;
    do {
        tmp[n++] = (char)('0' + value % 10);
        value /= 10;
    } while (value);
    do *out++ = tmp[--n]; while (n);
    return out;
}

static __attribute__((always_inline)) inline char *duck_write_i64(char *out, duck_i64 value) {
    if (value < 0) {
        *out++ = '-';
        return duck_write_u64(out, (duck_u64)(-value));
    }
    return duck_write_u64(out, (duck_u64)value);
}

static __attribute__((always_inline, noreturn)) inline void duck_exit(void) {
    __asm__ volatile("mov $60,%%eax;xor %%edi,%%edi;syscall" ::: "rax", "rdi", "rcx", "r11", "memory");
    __builtin_unreachable();
}

#endif


typedef unsigned int u32;
typedef unsigned long u64;

#define MAXS 1000005
#define MAXT 2000005
#define MAXN 500005
#define MAXQ 100005
#define SEGSZ 2097152

static u32 snext[MAXS][26], slink[MAXS], slen[MAXS], prefix_state[MAXN];
static u32 link_head[MAXS], link_to[MAXS], link_next[MAXS];
static u32 tin[MAXS], tout[MAXS], dfs_node[MAXS], dfs_edge[MAXS];
static u32 seg[SEGSZ], segbase;

static u32 tnext[MAXT][26], tlink[MAXT], tlen[MAXT];

static const char *qstr[MAXQ];
static u32 qlen[MAXQ], qleft[MAXQ], qnext[MAXQ], qhead[MAXN];
static u64 qans[MAXQ];

static __attribute__((always_inline)) inline u32 rd(const char **pp) {
    const char *p = *pp;
    while ((unsigned char)(*p - '0') > 9) ++p;
    u32 x = 0;
    do { x = x * 10u + (u32)(*p++ - '0'); }
    while ((unsigned char)(*p - '0') <= 9);
    *pp = p;
    return x;
}

static __attribute__((always_inline)) inline char *putu(char *p, u64 x) {
    char s[24]; u32 n = 0;
    do { s[n++] = (char)('0' + x % 10); x /= 10; } while (x);
    do { *p++ = s[--n]; } while (n);
    *p++ = '\n';
    return p;
}

static __attribute__((always_inline)) inline u32 sam_add_s(u32 c, u32 pos,
                                                            u32 *tot, u32 *last) {
    u32 p = *last, np = ++*tot;
    slen[np] = slen[p] + 1; *last = np; prefix_state[pos] = np;
    while (p && !snext[p][c]) snext[p][c] = np, p = slink[p];
    if (!p) slink[np] = 1;
    else {
        u32 q = snext[p][c];
        if (slen[q] == slen[p] + 1) slink[np] = q;
        else {
            u32 nq = ++*tot;
            __builtin_memcpy(snext[nq], snext[q], sizeof(snext[q]));
            slen[nq] = slen[p] + 1; slink[nq] = slink[q];
            while (p && snext[p][c] == q) snext[p][c] = nq, p = slink[p];
            slink[q] = slink[np] = nq;
        }
    }
    return np;
}

static void build_euler(u32 states) {
    __builtin_memset(link_head, 0, (states + 1) * sizeof(*link_head));
    u32 ec = 0;
    for (u32 v = 2; v <= states; ++v) {
        u32 p = slink[v];
        link_to[++ec] = v; link_next[ec] = link_head[p]; link_head[p] = ec;
    }
    u32 timer = 1, top = 0;
    dfs_node[0] = 1; dfs_edge[0] = link_head[1]; tin[1] = 1;
    for (;;) {
        u32 e = dfs_edge[top];
        if (e) {
            dfs_edge[top] = link_next[e];
            u32 v = link_to[e];
            ++top; dfs_node[top] = v; dfs_edge[top] = link_head[v]; tin[v] = ++timer;
        } else {
            tout[dfs_node[top]] = timer;
            if (!top) break;
            --top;
        }
    }
}

static __attribute__((always_inline)) inline void activate(u32 state, u32 value) {
    u32 x = segbase + tin[state] - 1;
    seg[x] = value;
    while (x >>= 1) {
        u32 a = seg[x << 1], b = seg[x << 1 | 1];
        u32 v = a > b ? a : b;
        if (seg[x] == v) break;
        seg[x] = v;
    }
}

static __attribute__((always_inline)) inline u32 rightmost(u32 state) {
    u32 l = segbase + tin[state] - 1, r = segbase + tout[state] - 1, ans = 0;
    while (l <= r) {
        if (l & 1) { if (seg[l] > ans) ans = seg[l]; ++l; }
        if (!(r & 1)) { if (seg[r] > ans) ans = seg[r]; --r; }
        l >>= 1; r >>= 1;
    }
    return ans;
}

static __attribute__((always_inline)) inline u32 sam_add_t(u32 c, u32 *tot, u32 *last) {
    u32 p = *last, np = ++*tot;
    tlen[np] = tlen[p] + 1; *last = np;
    while (p && !tnext[p][c]) tnext[p][c] = np, p = tlink[p];
    if (!p) tlink[np] = 1;
    else {
        u32 q = tnext[p][c];
        if (tlen[q] == tlen[p] + 1) tlink[np] = q;
        else {
            u32 nq = ++*tot;
            __builtin_memcpy(tnext[nq], tnext[q], sizeof(tnext[q]));
            tlen[nq] = tlen[p] + 1; tlink[nq] = tlink[q];
            while (p && tnext[p][c] == q) tnext[p][c] = nq, p = tlink[p];
            tlink[q] = tlink[np] = nq;
        }
    }
    return np;
}

static u64 solve_query(const char *s, u32 n, u32 left) {
    static u32 previous_states;
    __builtin_memset(tnext[1], 0, (u64)previous_states * sizeof(tnext[1]));
    tlink[1] = tlen[1] = 0;
    u32 ttot = 1, tlast = 1, sp = 1, match = 0;
    u64 ans = 0;
    for (u32 i = 0; i < n; ++i) {
        u32 c = (u32)(s[i] - 'a');
        while (sp != 1 && !snext[sp][c]) {
            sp = slink[sp];
            if (match > slen[sp]) match = slen[sp];
        }
        if (snext[sp][c]) sp = snext[sp][c], ++match;
        else sp = 1, match = 0;

        while (match) {
            u32 endpoint = rightmost(sp);
            if (endpoint + 1 >= left + match) break;
            u32 parent = slink[sp];
            u32 allowed = endpoint >= left ? endpoint - left + 1 : 0;
            if (allowed && allowed >= slen[parent]) {
                match = allowed;
                if (allowed == slen[parent]) sp = parent;
                break;
            }
            sp = parent; match = slen[sp];
        }
        if (!match) sp = 1;

        u32 cur = sam_add_t(c, &ttot, &tlast);
        u32 low = tlen[tlink[cur]];
        if (match > low) low = match;
        if (low < tlen[cur]) ans += tlen[cur] - low;
    }
    previous_states = ttot;
    return ans;
}

__attribute__((noreturn))
void __libc_start_main(void *unused, long argc, char **argv) {
    (void)unused;
    DuckInfo *info = duck_info(argc, argv);
    const char *p = info->stdin_ptr;
    while ((unsigned char)(*p - 'a') >= 26) ++p;
    const char *source = p;
    while ((unsigned char)(*p - 'a') < 26) ++p;
    u32 n = (u32)(p - source);

    slink[1] = slen[1] = 0;
    u32 stot = 1, slast = 1;
    for (u32 i = 1; i <= n; ++i) sam_add_s((u32)(source[i - 1] - 'a'), i, &stot, &slast);
    build_euler(stot);
    segbase = 1; while (segbase < stot) segbase <<= 1;
    __builtin_memset(seg, 0, (segbase << 1) * sizeof(*seg));

    u32 Q = rd(&p);
    __builtin_memset(qhead, 0xff, (n + 1) * sizeof(*qhead));
    for (u32 qi = 0; qi < Q; ++qi) {
        while ((unsigned char)(*p - 'a') >= 26) ++p;
        qstr[qi] = p;
        while ((unsigned char)(*p - 'a') < 26) ++p;
        qlen[qi] = (u32)(p - qstr[qi]);
        qleft[qi] = rd(&p); u32 r = rd(&p);
        qnext[qi] = qhead[r]; qhead[r] = qi;
    }
    for (u32 r = 1; r <= n; ++r) {
        activate(prefix_state[r], r);
        for (u32 qi = qhead[r]; qi != ~0u; qi = qnext[qi])
            qans[qi] = solve_query(qstr[qi], qlen[qi], qleft[qi]);
    }
    char *out = info->stdout_ptr;
    for (u32 qi = 0; qi < Q; ++qi) out = putu(out, qans[qi]);
    info->stdout_size = (u64)(out - info->stdout_ptr);
    duck_exit();
}

int main(void) {}

评测结果