代码

// 【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: element scan at the two ends + 2-level block hierarchy ----------
static const int B0 = 16;        // positions per level-0 block
static const int B1 = 64;        // level-0 blocks per super-block
static int nb0, nb1, stN;
static int *val, *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 = (int *)calloc(n + B0 + 2, 4);
    bmax0 = (int *)calloc(nb0 + 2, 4);
    pre1 = (int *)calloc(nb0 + 2, 4);
    suf1 = (int *)calloc(nb0 + 2, 4);
    bmax1 = (int *)calloc(nb1 + 2, 4);
    stree = (int *)calloc(2 * stN, 4);
}
static inline void stSet(int pos, int v) {
    val[pos] = v;
    int b = (pos - 1) / B0;
    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;
    int res = 0;
    if (b0l == b0r) {
        for (int i = l; i <= r; i++) if (val[i] > res) res = val[i];
        return res;
    }
    int e = (b0l + 1) * B0;
    for (int i = l; i <= e; i++) if (val[i] > res) res = val[i];
    int s = b0r * B0 + 1;
    for (int i = s; i <= r; i++) if (val[i] > res) res = val[i];
    int a = b0l + 1, bb = b0r - 1;
    if (a <= bb) {
        int sbl = a / B1, sbr = bb / B1;
        if (sbl == sbr) {
            for (int i = a; i <= bb; i++) if (bmax0[i] > res) res = bmax0[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;
                }
            }
            int e1 = (sbl + 1) * B1; if (e1 > bb + 1) e1 = bb + 1;
            for (int i = a; i < e1; i++) if (bmax0[i] > res) res = bmax0[i];
            int s2 = sbr * B1; if (s2 < a) s2 = a;
            for (int i = s2; i <= bb; i++) if (bmax0[i] > res) res = bmax0[i];
        }
    }
    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 cmap[256];
    for (int i = 0; i < 256; i++) cmap[i] = -1;
    int sigma = 0;
    for (int i = 0; i < nS; i++) { unsigned char u = (unsigned char)S[i]; if (cmap[u] < 0) cmap[u] = sigma++; }
    if (sigma == 0) sigma = 1;
    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 * sigma, 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 = cmap[(unsigned char)S[i]];
        int cur = ++sz;
        len[cur] = len[last] + 1;
        link[cur] = 0;
        int p = last;
        while (p && !ch[(size_t)p * sigma + c]) { ch[(size_t)p * sigma + c] = cur; p = link[p]; }
        if (!p) link[cur] = 1;
        else {
            int q = ch[(size_t)p * sigma + 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 * sigma], &ch[(size_t)q * sigma], sigma * sizeof(int));
                while (p && ch[(size_t)p * sigma + c] == q) { ch[(size_t)p * sigma + c] = clone; p = link[p]; }
                link[q] = clone;
                link[cur] = clone;
            }
        }
        last = cur;
        lastPos[i + 1] = last;
    }

    // ---------- link tree: sibling lists + preorder + parent accumulation ----------
    vector<int> firstChild(sz + 1, 0), nextSib(sz + 1, 0);
    for (int v = 2; v <= sz; v++) { int p = link[v]; nextSib[v] = firstChild[p]; firstChild[p] = v; }
    vector<int> tin(sz + 1, 0), szsub(sz + 1, 1), ord(sz + 1, 0);
    vector<unsigned long long> mmE(sz + 1, ((unsigned long long)(nS + 1) << 20));
    for (int i = 1; i <= nS; i++) { int u = lastPos[i]; mmE[u] = ((unsigned long long)i << 20) | (unsigned)i; }
    {
        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 c2 = firstChild[v]; c2; c2 = nextSib[c2]) stk.push_back(c2);
        }
        for (int t = timer; t >= 1; t--) {
            int v = ord[t], p = link[v];
            if (!p) continue;
            szsub[p] += szsub[v];
            unsigned long long e2 = mmE[v], e = mmE[p];
            if ((e2 >> 20) < (e >> 20)) e = (e & 0xFFFFFULL) | (e2 & ~0xFFFFFULL);
            if ((e2 & 0xFFFFFULL) > (e & 0xFFFFFULL)) e = (e & ~0xFFFFFULL) | (e2 & 0xFFFFFULL);
            mmE[p] = e;
        }
    }
    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);

    static int tmap[256], tmapGen[256];
    int tgenStamp = 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;
            tgenStamp++;
            int tsigma = 0;
            for (int z = 0; z < m; z++) {
                unsigned char u = (unsigned char)T[z];
                if (tmapGen[u] != tgenStamp) { tmapGen[u] = tgenStamp; tmap[u] = tsigma++; }
            }
            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 = cmap[(unsigned char)T[i - 1]];
                // --- insert into SAM of T ---
                {
                    int tc = tmap[(unsigned char)T[i - 1]];
                    int cur = ++tsz;
                    tlen[cur] = tlen[tlast] + 1;
                    tlink[cur] = 0;
                    int p = tlast;
                    while (p && !tch[(size_t)p * AL + tc]) {
                        tch[(size_t)p * AL + tc] = cur;
                        tdirty.push_back((int)((size_t)p * AL + tc));
                        p = tlink[p];
                    }
                    if (!p) tlink[cur] = 1;
                    else {
                        int qq2 = tch[(size_t)p * AL + tc];
                        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 + tc] == qq2) {
                                tch[(size_t)p * AL + tc] = clone;
                                tdirty.push_back((int)((size_t)p * AL + tc));
                                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 = (c < 0) ? 0 : ch[(size_t)v * sigma + 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;
}

评测结果