代码

// 【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 (whole buffer) ----------
static char inbuf[1 << 23];
static size_t inpos = 0;
static inline int gc() { return (unsigned char)inbuf[inpos++]; }
static inline int rdint() {
    while (inbuf[inpos] < '0' || inbuf[inpos] > '9') inpos++;
    int x = 0;
    while (inbuf[inpos] >= '0' && inbuf[inpos] <= '9') { x = x * 10 + (inbuf[inpos] - '0'); inpos++; }
    return x;
}

static const int AL = 26;

// ---------- range max: 16-blocks (pre/suf) -> 1024-superblocks (pre/suf) -> small tree ----------
static const int B0 = 16;        // positions per level-0 block
static const int B1 = 64;        // level-0 blocks per super-block (1024 positions)
static int nb0, nb1, stN;
static vector<int> val, pre0, suf0, bmax0, pre1, suf1, bmax1, stree;

static void stInit(int n) {
    nb0 = (n + B0 - 1) / B0;
    nb1 = (nb0 + B1 - 1) / B1;
    stN = 1; while (stN < nb1) stN <<= 1;
    val.assign(n + B0 + 2, 0);
    pre0.assign(n + B0 + 2, 0);
    suf0.assign(n + B0 + 2, 0);
    bmax0.assign(nb0 + 2, 0);
    pre1.assign(nb0 + 2, 0);
    suf1.assign(nb0 + 2, 0);
    bmax1.assign(nb1 + 2, 0);
    stree.assign(2 * stN, 0);
}
// activations carry strictly increasing values
static inline void stSet(int pos, int v) {
    val[pos] = v;
    int b = (pos - 1) / B0;
    int s = b * B0 + 1, e = s + B0 - 1;
    for (int q = s; q <= pos; q++) suf0[q] = v;
    for (int q = pos; q <= e; q++) pre0[q] = v;
    if (v > bmax0[b]) {
        bmax0[b] = v;
        int sb = b / B1;
        int bs = sb * B1, be = bs + B1 - 1;
        if (be >= nb0) be = nb0 - 1;
        for (int q = bs; q <= b; q++) suf1[q] = v;
        for (int q = b; q <= be; q++) pre1[q] = v;
        if (v > bmax1[sb]) {
            bmax1[sb] = v;
            int i = sb + stN;
            stree[i] = v;
            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 b0l = (l - 1) / B0, b0r = (r - 1) / B0;
    if (b0l == b0r) {
        const int *v = val.data();
        int res = 0;
        for (int i = l; i <= r; i++) if (v[i] > res) res = v[i];
        return res;
    }
    int res = suf0[l] > pre0[r] ? suf0[l] : pre0[r];
    int a = b0l + 1, bb = b0r - 1;
    if (a <= bb) {
        int sbl = a / B1, sbr = bb / B1;
        if (sbl == sbr) {
            const int *bm = bmax0.data();
            for (int i = a; i <= bb; i++) if (bm[i] > res) res = bm[i];
        } else {
            if (suf1[a] > res) res = suf1[a];
            if (pre1[bb] > res) res = pre1[bb];
            int ta = sbl + 1, tb = sbr - 1;
            if (ta <= tb) {
                int x = ta + stN, y = tb + stN;
                while (x <= y) {
                    if (x & 1) { if (stree[x] > res) res = stree[x]; x++; }
                    if (!(y & 1)) { if (stree[y] > res) res = stree[y]; y--; }
                    x >>= 1; y >>= 1;
                }
            }
        }
    }
    return res;
}

int main() {
    {
        size_t len = 0, r;
        while (len < sizeof(inbuf) - 1 && (r = fread(inbuf + len, 1, sizeof(inbuf) - 1 - len, stdin)) > 0) len += r;
        inbuf[len] = 0;
    }
    // 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;
        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<unsigned long long> mmE(sz + 1, ((unsigned long long)(nS + 1) << 20));
    {
        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 i = 1; i <= nS; i++) { int u = lastPos[i]; mmE[u] = ((unsigned long long)i << 20) | (unsigned)i; }
        for (int t = timer; t >= 1; t--) {
            int v = ord[t];
            int s = 1;
            for (int k = cstart[v]; k < cstart[v + 1]; k++) {
                int c2 = childList[k];
                s += szsub[c2];
                unsigned long long e2 = mmE[c2];
                if ((e2 >> 20) < (mmE[v] >> 20)) mmE[v] = (mmE[v] & 0xFFFFFULL) | (e2 & ~0xFFFFFULL);
                if ((e2 & 0xFFFFFULL) > (mmE[v] & 0xFFFFFULL)) mmE[v] = (mmE[v] & ~0xFFFFFULL) | (e2 & 0xFFFFFULL);
            }
            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);
    vector<int> tdirty;
    tdirty.reserve((size_t)tmaxSt * 2);

    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;
            for (size_t z = 0; z < tdirty.size(); z++) tch[tdirty[z]] = 0;
            tdirty.clear();
            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;
                    int p = tlast;
                    while (p && !tch[(size_t)p * AL + c]) {
                        tch[(size_t)p * AL + c] = cur;
                        tdirty.push_back((int)((size_t)p * AL + c));
                        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];
                            {
                                const int *src = &tch[(size_t)qq2 * AL];
                                int *dst = &tch[(size_t)clone * AL];
                                for (int z = 0; z < AL; z++)
                                    if (src[z]) { dst[z] = src[z]; tdirty.push_back((int)((size_t)clone * AL + z)); }
                            }
                            while (p && tch[(size_t)p * AL + c] == qq2) {
                                tch[(size_t)p * AL + c] = clone;
                                tdirty.push_back((int)((size_t)p * AL + c));
                                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) {
                        int need = qq + L;
                        unsigned long long e = mmE[nv];
                        int lo = (int)(e >> 20), hi = (int)(e & 0xFFFFFULL);
                        int ok;
                        if (lo > r || hi < need) ok = 0;                 // no occurrence can fit
                        else if (lo >= need) ok = 1;                     // unique/leftmost fits
                        else ok = stMax(tin[nv], tin[nv] + szsub[nv] - 1) >= need;
                        if (ok) { 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;
}

评测结果