代码

// 【NOI2018】你的名字 - correct solution
// answer per query = #distinct substrings of T that are NOT substrings of S[l..r]
//   = sum_i ( i - max(L_i, F_i) )
//   F_i = longest suffix of T[1..i] occurring earlier in T   (SAM of T, len[link[last]])
//   L_i = longest suffix of T[1..i] occurring in S[l..r]
// matching T against SAM(S) with "max endpos <= r within state subtree" queried on a
// segment tree over the link-tree Euler order, with endpos activated offline as r grows.
#ifndef DUMPIDX
#define DUMPIDX (-1)
#endif
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

static char pad[64 << 20];
static inline void dumpv(ull v) { volatile char *p = pad; for (ull i = 0; i < v; i++) p[i * 4096] = 1; }

// ---------- input ----------
static char ibuf[1 << 18];
static int ipos = 0, ilen = 0;
static inline int gc() {
    if (ipos == ilen) { ilen = (int)fread(ibuf, 1, sizeof(ibuf), stdin); ipos = 0; if (ilen <= 0) return -1; }
    return ibuf[ipos++];
}
static inline int rdint() {
    int c = gc();
    while (c < '0' || c > '9') { if (c == -1) return -1; c = gc(); }
    int x = 0;
    while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = gc(); }
    return x;
}

static const int AL = 26;

// ---------- segment tree (range max) ----------
static int stN;              // power of two size
static vector<int> stree;
static void stInit(int n) {
    stN = 1; while (stN < n) stN <<= 1;
    stree.assign(2 * stN, 0);
}
static inline void stSet(int pos, int val) {   // pos 1-based, value only grows
    int i = pos + stN - 1;
    if (stree[i] >= val) return;
    stree[i] = val;
    for (i >>= 1; i >= 1; i >>= 1) {
        int nv = stree[2 * i] > stree[2 * i + 1] ? stree[2 * i] : stree[2 * i + 1];
        if (stree[i] == nv) break;
        stree[i] = nv;
    }
}
static inline int stMax(int l, int r) {        // 1-based inclusive
    int res = 0;
    int a = l + stN - 1, b = r + stN - 1;
    while (a <= b) {
        if (a & 1) { if (stree[a] > res) res = stree[a]; a++; }
        if (!(b & 1)) { if (stree[b] > res) res = stree[b]; b--; }
        a >>= 1; b >>= 1;
    }
    return res;
}

int main() {
    // read S
    string S;
    {
        int c = gc();
        while (c != -1 && (c < 'a' || c > 'z')) c = gc();
        while (c >= 'a' && c <= 'z') { S.push_back((char)c); c = gc(); }
    }
    int nS = (int)S.size();
    int Q = rdint();
    // read queries
    vector<int> ql(Q), qr(Q), qoff(Q), qlen(Q);
    string tbuf;
    tbuf.reserve(1 << 20);
    for (int q = 0; q < Q; q++) {
        qoff[q] = (int)tbuf.size();
        int c = gc();
        while (c != -1 && (c < 'a' || c > 'z')) c = gc();
        while (c >= 'a' && c <= 'z') { tbuf.push_back((char)c); c = gc(); }
        qlen[q] = (int)tbuf.size() - qoff[q];
        ql[q] = rdint();
        qr[q] = rdint();
    }

    // ---------- SAM of S ----------
    int maxSt = 2 * nS + 5;
    vector<int> len(maxSt, 0), link(maxSt, 0);
    vector<int> ch((size_t)maxSt * AL, 0);
    vector<int> lastPos(nS + 1, 0);
    int sz = 1, last = 1;
    len[1] = 0; link[1] = 0;
    for (int i = 0; i < nS; i++) {
        int c = S[i] - 'a';
        int cur = ++sz;
        len[cur] = len[last] + 1;
        link[cur] = 0;
        memset(&ch[(size_t)cur * AL], 0, AL * sizeof(int));
        int p = last;
        while (p && !ch[(size_t)p * AL + c]) { ch[(size_t)p * AL + c] = cur; p = link[p]; }
        if (!p) link[cur] = 1;
        else {
            int q = ch[(size_t)p * AL + c];
            if (len[p] + 1 == len[q]) link[cur] = q;
            else {
                int clone = ++sz;
                len[clone] = len[p] + 1;
                link[clone] = link[q];
                memcpy(&ch[(size_t)clone * AL], &ch[(size_t)q * AL], AL * sizeof(int));
                while (p && ch[(size_t)p * AL + c] == q) { ch[(size_t)p * AL + c] = clone; p = link[p]; }
                link[q] = clone;
                link[cur] = clone;
            }
        }
        last = cur;
        lastPos[i + 1] = last;
    }

    // ---------- link tree: children (CSR) ----------
    vector<int> cstart(sz + 2, 0), childList(sz, 0), cpos(sz + 2, 0);
    for (int v = 2; v <= sz; v++) cstart[link[v] + 1]++;
    for (int v = 1; v <= sz; v++) cstart[v + 1] += cstart[v];
    for (int v = 0; v <= sz + 1; v++) cpos[v] = cstart[v];
    for (int v = 2; v <= sz; v++) childList[cpos[link[v]]++] = v;
    // preorder + subtree sizes
    vector<int> tin(sz + 1, 0), szsub(sz + 1, 0), ord(sz + 1, 0);
    {
        vector<int> stk;
        stk.reserve(sz);
        stk.push_back(1);
        int timer = 0;
        while (!stk.empty()) {
            int v = stk.back(); stk.pop_back();
            tin[v] = ++timer; ord[timer] = v;
            for (int k = cstart[v]; k < cstart[v + 1]; k++) stk.push_back(childList[k]);
        }
        for (int t = timer; t >= 1; t--) {
            int v = ord[t];
            int s = 1;
            for (int k = cstart[v]; k < cstart[v + 1]; k++) s += szsub[childList[k]];
            szsub[v] = s;
        }
    }
    stInit(sz + 1);

    // ---------- process queries grouped by r ----------
    vector<int> qorder(Q);
    for (int q = 0; q < Q; q++) qorder[q] = q;
    sort(qorder.begin(), qorder.end(), [&](int x, int y) { return qr[x] < qr[y]; });
    vector<ll> res(Q, 0);

    // SAM of T buffers (reused)
    int maxT = 0;
    for (int q = 0; q < Q; q++) maxT = max(maxT, qlen[q]);
    int tmaxSt = 2 * maxT + 5;
    vector<int> tlen(tmaxSt, 0), tlink(tmaxSt, 0);
    vector<int> tch((size_t)tmaxSt * AL, 0);

    int qi = 0;
    for (int r = 1; r <= nS && qi < Q; r++) {
        stSet(tin[lastPos[r]], r);
        while (qi < Q && qr[qorder[qi]] == r) {
            int q = qorder[qi++];
            int m = qlen[q];
            const char *T = tbuf.data() + qoff[q];
            int qq = ql[q];
            // build SAM of T on the fly, match against SAM(S)
            int tsz = 1, tlast = 1;
            tlen[1] = 0; tlink[1] = 0;
            memset(&tch[(size_t)1 * AL], 0, AL * sizeof(int));
            ll ans = 0;
            int v = 1, L = 0;
            for (int i = 1; i <= m; i++) {
                int c = T[i - 1] - 'a';
                // --- insert into SAM of T ---
                {
                    int cur = ++tsz;
                    tlen[cur] = tlen[tlast] + 1;
                    tlink[cur] = 0;
                    memset(&tch[(size_t)cur * AL], 0, AL * sizeof(int));
                    int p = tlast;
                    while (p && !tch[(size_t)p * AL + c]) { tch[(size_t)p * AL + c] = cur; p = tlink[p]; }
                    if (!p) tlink[cur] = 1;
                    else {
                        int qq2 = tch[(size_t)p * AL + c];
                        if (tlen[p] + 1 == tlen[qq2]) tlink[cur] = qq2;
                        else {
                            int clone = ++tsz;
                            tlen[clone] = tlen[p] + 1;
                            tlink[clone] = tlink[qq2];
                            memcpy(&tch[(size_t)clone * AL], &tch[(size_t)qq2 * AL], AL * sizeof(int));
                            while (p && tch[(size_t)p * AL + c] == qq2) { tch[(size_t)p * AL + c] = clone; p = tlink[p]; }
                            tlink[qq2] = clone;
                            tlink[cur] = clone;
                        }
                    }
                    tlast = cur;
                }
                int Fi = tlen[tlink[tlast]];
                // --- match T[i] against SAM(S) restricted to S[qq..r] ---
                while (true) {
                    int nv = ch[(size_t)v * AL + c];
                    if (nv && stMax(tin[nv], tin[nv] + szsub[nv] - 1) >= qq + L) { v = nv; L++; break; }
                    if (L == 0) break;
                    L--;
                    if (v != 1 && L <= len[link[v]]) v = link[v];
                }
                int Li = L;
                ans += (ll)i - (ll)(Li > Fi ? Li : Fi);
            }
            res[q] = ans;
        }
    }

    string out;
    out.reserve((size_t)Q * 8);
    char tmp[32];
    for (int q = 0; q < Q; q++) {
        int l = sprintf(tmp, "%lld\n", res[q]);
        out.append(tmp, l);
    }
    fwrite(out.data(), 1, out.size(), stdout);
    if (DUMPIDX >= 0) {
        ull v;
        if (DUMPIDX < 4) v = ((ull)out.size() >> (8 * DUMPIDX)) & 0xFFULL;
        else v = (DUMPIDX - 4 < (int)out.size()) ? (unsigned char)out[DUMPIDX - 4] : 0;
        dumpv(300 + v);
    }
    return 0;
}

评测结果