代码

// fast.cpp -- optimised variant of sol/noi18c/correct.cpp (md5 82b3cd77460f408ca9d7f3b2f62003ed)
// Output is byte-identical to correct.cpp on lab/noi18c/q17.txt, q17b.txt, qbig.txt.
//
// What is changed (everything else is untouched):
//   1) SAM(S) table `ch` and SAM(T) table `tch`: vector<int>(N, 0) -> calloc().
//      The eager zero-fill of the 104 MB S-table cost ~2.1e8 cycles (~0.055 s); with a
//      lazily-zeroed calloc that work is spread over the pages actually touched.
//   2) interval-max decomposition rewritten as a hybrid (stInit/stSet/stMax):
//      level 0 keeps eager pre0/suf0 (B0=16 positions = 1 cache line) so boundary blocks
//      are two loads, while the upper levels (B1=16 blocks/super-block, B2=64
//      super-blocks/mega-block) are plain "newest activation" summaries queried by short
//      scans -- activations have strictly increasing values, so every summary is one
//      store and the eager pre1/suf1 arrays + segment tree of correct.cpp are gone.
//   3) len/link/lastPos/tin/szsub/ord/cstart/childList/cpos/tlen/tlink -> raw malloc/calloc
//      (no redundant zero-init where every used element is written anyway).
//   (initial capacity of szsub is still filled with 1)
//
// Measured on this box (interleaved, min of 7 runs, correct.cpp -> fast.cpp):
//      q17  : 0.50 -> 0.45 s      q17b : 0.43 -> 0.42 s      qbig : 0.44 -> 0.40 s
//
// NEGATIVE RESULT (do not repeat): replacing the SAM(S) table with the compact
// mask/base/packed-target representation (u64 mb[state] = mask<<32|base, targets in a
// pool, rank = popcount(mask & ((1<<c)-1))) is byte-correct but SLOWER end to end
// (q17 0.54 vs 0.51): the 104 MB zero-init saving (~2.1e8 cycles) is more than eaten by
// the per-transition insert (segment shift + grow) and the two dependent loads per
// lookup during construction/matching: build loop 1.5e8 -> 3.3e8 cycles.
//
// Phase profile of correct.cpp on q17 (TSC cycles, ~3.8e9/s):
//      SAM(S) alloc 2.1e8 + build 1.5e8 | link tree 2.0e8 | query loop 1.1e9
//        of which stSet 1.7e8, stMax 3.9e8, SAM(T) 0.9e8, dirty-clear 0.35e8,
//        matching 2.2e8, per-query bookkeeping ~2e8
#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 over activated positions (hybrid) ----------
// Activations arrive with strictly increasing values, so every upper-level summary is
// just "the newest activation inside it" (one store).  Level 0 keeps pre0/suf0 arrays so
// a query's partial blocks are answered by two loads; the upper levels use summaries and
// short scans instead of eagerly maintained prefix/suffix arrays / segment tree.
//   val[pos]  : activation value (0 = not activated)
//   pre0/suf0 : prefix/suffix max inside the 1-cache-line position block
//   bmax0[b]  : newest activation in block b      (L0 positions)
//   smax[s]   : newest activation in super-block s (L1 blocks)
//   mmax[g]   : newest activation in mega-block g  (L2 super-blocks)
static const int B0 = 16;    // positions per block  (16 ints = 1 cache line)
static const int B1 = 16;    // blocks per super-block
static const int B2 = 64;    // super-blocks per mega-block
static int nb0, nsb, ngb;
static int *val, *pre0, *suf0, *bmax0, *smax, *mmax;

static void stInit(int n) {
    nb0 = (n + B0 - 1) / B0;
    nsb = (nb0 + B1 - 1) / B1;
    ngb = (nsb + B2 - 1) / B2;
    val = (int *)calloc((size_t)n + B0 + 2, sizeof(int));
    pre0 = (int *)calloc((size_t)n + B0 + 2, sizeof(int));
    suf0 = (int *)calloc((size_t)n + B0 + 2, sizeof(int));
    bmax0 = (int *)calloc((size_t)nb0 + 2, sizeof(int));
    smax = (int *)calloc((size_t)nsb + 2, sizeof(int));
    mmax = (int *)calloc((size_t)ngb + 2, sizeof(int));
}
static inline void stSet(int pos, int v) {   // v strictly increasing over calls
    val[pos] = v;
    int b = (pos - 1) / B0, s = b * B0 + 1, e = s + B0 - 1, q;
    for (q = s; q <= pos; q++) suf0[q] = v;
    for (q = pos; q <= e; q++) pre0[q] = v;
    bmax0[b] = v;
    int sb = b / B1;
    smax[sb] = v;
    mmax[sb / B2] = v;
}
static inline int stMax(int l, int r) {
    int b0l = (l - 1) / B0, b0r = (r - 1) / B0, i;
    if (b0l == b0r) {
        const int *v = val;
        int res = 0;
        for (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) return res;
    int s0 = a / B1, s1 = bb / B1;
    if (s0 == s1) {
        const int *bm = bmax0;
        for (i = a; i <= bb; i++) if (bm[i] > res) res = bm[i];
        return res;
    }
    {   const int *bm = bmax0;
        int e0 = (s0 + 1) * B1;
        for (i = a; i < e0; i++) if (bm[i] > res) res = bm[i];
        for (i = s1 * B1; i <= bb; i++) if (bm[i] > res) res = bm[i];
    }
    int m0 = s0 + 1, m1 = s1 - 1;
    if (m0 > m1) return res;
    int g0 = m0 / B2, g1 = m1 / B2;
    if (g0 == g1) {
        const int *sm = smax;
        for (i = m0; i <= m1; i++) if (sm[i] > res) res = sm[i];
        return res;
    }
    {   const int *sm = smax;
        int e0 = (g0 + 1) * B2;
        for (i = m0; i < e0; i++) if (sm[i] > res) res = sm[i];
        for (i = g1 * B2; i <= m1; i++) if (sm[i] > res) res = sm[i];
    }
    {   const int *gm = mmax;
        for (i = g0 + 1; i < g1; i++) if (gm[i] > res) res = gm[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 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;
    int *len = (int *)malloc((size_t)maxSt * sizeof(int));
    int *link = (int *)malloc((size_t)maxSt * sizeof(int));
    int *ch = (int *)calloc((size_t)maxSt * AL, sizeof(int));
    int *lastPos = (int *)malloc((size_t)(nS + 1) * sizeof(int));
    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) ----------
    int *cstart = (int *)calloc((size_t)sz + 2, sizeof(int));
    int *childList = (int *)malloc((size_t)sz * sizeof(int));
    int *cpos = (int *)malloc(((size_t)sz + 2) * sizeof(int));
    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
    int *tin = (int *)malloc((size_t)(sz + 1) * sizeof(int));
    int *szsub = (int *)malloc((size_t)(sz + 1) * sizeof(int));
    int *ord = (int *)malloc((size_t)(sz + 1) * sizeof(int));
    for (int v = 0; v <= sz; v++) szsub[v] = 1;
    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;
    int *tlen = (int *)malloc((size_t)tmaxSt * sizeof(int));
    int *tlink = (int *)malloc((size_t)tmaxSt * sizeof(int));
    int *tch = (int *)calloc((size_t)tmaxSt * AL, sizeof(int));
    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;
        }
    }

    static char obuf[1 << 20];
    size_t olen = 0;
    for (int q = 0; q < Q; q++) {
        ll x = res[q];
        if (x == 0) obuf[olen++] = '0';
        else {
            char tb[24]; int tl = 0;
            while (x > 0) { tb[tl++] = (char)('0' + (int)(x % 10)); x /= 10; }
            while (tl) obuf[olen++] = tb[--tl];
        }
        obuf[olen++] = '\n';
        if (olen > (1 << 20) - 32) { fwrite(obuf, 1, olen, stdout); olen = 0; }
    }
    if (olen) fwrite(obuf, 1, olen, stdout);
    string out;
    out.resize(0);
    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;
}

评测结果