代码

// noi17b 【NOI2017】蚯蚓排队
// Maintain counts of every length-k window (k <= Kmax over queries) in a hash
// table keyed by (64-bit rolling hash, k).  Merges/splits only change windows
// crossing the junction: walk back/forward up to Kmax-1 worms and rebuild them.
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sys/auxv.h>
using namespace std;
struct DI { unsigned long long abi; const char *in; unsigned long long insz; char *out;
            unsigned long long outlim; unsigned long long outsz; char *err;
            unsigned long long errlim; unsigned long long errsz; const char *IB;
            unsigned long long IBlim; char *OB; unsigned long long OBlim; unsigned long long tscfreq; }
            __attribute__((packed));
typedef unsigned long long u64;
typedef unsigned int u32;

static const u64 MODP = 998244353ULL;
#define MAXN 200005

// ---------------- I/O ----------------
static char *inbuf;
static size_t inpos;
static inline int gc() { return (unsigned char)inbuf[inpos++]; }

static char obuf[1 << 25];
static char *outp = obuf;
static size_t olen = 0;
static unsigned short dig4[10000][4];
static inline void wnum(u64 x) {
    char t[24];
    int k = 0;
    while (x >= 10000) {
        unsigned r = (unsigned)(x % 10000); x /= 10000;
        t[k++] = (char)('0' + dig4[r][3]);
        t[k++] = (char)('0' + dig4[r][2]);
        t[k++] = (char)('0' + dig4[r][1]);
        t[k++] = (char)('0' + dig4[r][0]);
    }
    unsigned r = (unsigned)x;
    do { t[k++] = (char)('0' + r % 10); r /= 10; } while (r);
    while (k) outp[olen++] = t[--k];
    outp[olen++] = '\n';
}

// ---------------- hash table ----------------
static u64 *hkey;
static u32 *hval;
static u32 hmask;
static inline u32 *slot(u64 key) {
    if (!key) key = 0x9E3779B97F4A7C15ULL;
    u32 i = (u32)((key * 0x9E3779B97F4A7C15ULL) >> 40) & hmask;
    while (hkey[i] != 0 && hkey[i] != key) i = (i + 1) & hmask;
    if (hkey[i] == 0) { hkey[i] = key; hval[i] = 0; }
    return &hval[i];
}

static int n, m;
static unsigned char len_[MAXN];
static u32 prv[MAXN], nxt[MAXN];
static u64 pw[64];
static u64 base_;
static int K;

// left[i] = hash of the string len_[L[i]]..len_[L[i-1]] as a forward string
static u64 Lh[64];
static u64 Rh[64];
static unsigned char Lc[64], Rc[64];

static inline void addWindow(int k, u64 h, int delta) {
    u32 *c = slot((h << 6) | (u64)k);
    *c += delta;
}

int main() {
    {
        DI *di = (DI *)getauxval(0x6b637564ULL);
        if (di) outp = di->out;
        for (int v = 0; v < 10000; v++) {
            int x = v;
            dig4[v][3] = (unsigned short)(x % 10); x /= 10;
            dig4[v][2] = (unsigned short)(x % 10); x /= 10;
            dig4[v][1] = (unsigned short)(x % 10); x /= 10;
            dig4[v][0] = (unsigned short)(x % 10);
        }
    }
    inbuf = (char *)malloc(1 << 26);
    size_t got = fread(inbuf, 1, 1 << 26, stdin);
    (void)got;
    // ---- parse n, m ----
    while (inbuf[inpos] < '0' || inbuf[inpos] > '9') inpos++;
    { u64 x = 0; while (inbuf[inpos] >= '0' && inbuf[inpos] <= '9') { x = x * 10 + (inbuf[inpos] - '0'); inpos++; } n = (int)x; }
    while (inbuf[inpos] < '0' || inbuf[inpos] > '9') inpos++;
    { u64 x = 0; while (inbuf[inpos] >= '0' && inbuf[inpos] <= '9') { x = x * 10 + (inbuf[inpos] - '0'); inpos++; } m = (int)x; }
    {
        u64 x;
        for (int i = 1; i <= n; i++) {
            while (inbuf[inpos] < '0' || inbuf[inpos] > '9') inpos++;
            x = 0; while (inbuf[inpos] >= '0' && inbuf[inpos] <= '9') { x = x * 10 + (inbuf[inpos] - '0'); inpos++; }
            len_[i] = (unsigned char)x;
        }
    }
    // ---- first pass: find K = max k over queries, and count windows to size the table ----
    K = 1;
    {
        size_t save = inpos;
        for (int q = 0; q < m; q++) {
            while (inbuf[inpos] == '\n' || inbuf[inpos] == ' ' || inbuf[inpos] == '\r') inpos++;
            int op = inbuf[inpos] - '0';
            inpos++;
            if (op == 3) {
                while (inbuf[inpos] == ' ') inpos++;      // skip spaces
                {
                    char *sp2 = (char *)memchr(inbuf + inpos, ' ', 64 * 1024 * 1024 - inpos);
                    inpos = (size_t)(sp2 - inbuf);
                }
                while (inbuf[inpos] == ' ') inpos++;
                u64 x = 0; while (inbuf[inpos] >= '0' && inbuf[inpos] <= '9') { x = x * 10 + (inbuf[inpos] - '0'); inpos++; }
                if ((int)x > K) K = (int)x;
            } else {
                char *nl = (char *)memchr(inbuf + inpos, '\n', 64 * 1024 * 1024 - inpos);
                inpos = nl ? (size_t)(nl - inbuf) : inpos;
            }
        }
        inpos = save;
    }
    if (K > 50) K = 50;
    // table size: at most n*(K) live windows + churn; use 2^22
    {
        u32 sz = 1u << 22;
        while ((u64)sz * 3 < (u64)n * (K + 1) * 4 && sz < (1u << 26)) sz <<= 1;
        hkey = (u64 *)calloc(sz, sizeof(u64));
        hval = (u32 *)calloc(sz, sizeof(u32));
        hmask = sz - 1;
        if (!hkey || !hval) return 1;
    }
    base_ = 1000003ULL;
    pw[0] = 1;
    for (int i = 1; i <= K + 2; i++) pw[i] = pw[i - 1] * base_;
    // ---- init: each worm alone -> windows of length 1 ----
    for (int i = 1; i <= n; i++) {
        prv[i] = 0; nxt[i] = 0;
        addWindow(1, (u64)len_[i], 1);
    }
    // ---- process operations ----
    for (int q = 0; q < m; q++) {
        while (inbuf[inpos] == '\n' || inbuf[inpos] == ' ' || inbuf[inpos] == '\r') inpos++;
        int op = inbuf[inpos] - '0';
        inpos++;
        if (op == 1) {
            while (inbuf[inpos] < '0' || inbuf[inpos] > '9') inpos++;
            u64 x = 0; while (inbuf[inpos] >= '0' && inbuf[inpos] <= '9') { x = x * 10 + (inbuf[inpos] - '0'); inpos++; }
            int i = (int)x;
            while (inbuf[inpos] < '0' || inbuf[inpos] > '9') inpos++;
            x = 0; while (inbuf[inpos] >= '0' && inbuf[inpos] <= '9') { x = x * 10 + (inbuf[inpos] - '0'); inpos++; }
            int j = (int)x;
            // collect up to K-1 worms ending at i (walk back)
            int nl = 0; {
                int p = i;
                while (p && nl < K) { Lc[nl++] = len_[p]; p = prv[p]; }
            }
            // Lh[a] = hash of Lc[a-1..0] read forward (i.e. the a worms ending at i)
            Lh[0] = 0;
            for (int a = 1; a <= nl; a++) Lh[a] = Lh[a - 1] + (u64)Lc[a - 1] * pw[a - 1];
            int nr = 0; {
                int p = j;
                while (p && nr < K) { Rc[nr++] = len_[p]; p = nxt[p]; }
            }
            Rh[0] = 0;
            for (int b = 1; b <= nr; b++) Rh[b] = Rh[b - 1] * base_ + Rc[b - 1];
            for (int a = 1; a <= nl; a++) {
                int bmax = K - a;
                if (bmax > nr) bmax = nr;
                for (int b = 1; b <= bmax; b++) addWindow(a + b, Lh[a] * pw[b] + Rh[b], 1);
            }
            nxt[i] = (u32)j; prv[j] = (u32)i;
        } else if (op == 2) {
            while (inbuf[inpos] < '0' || inbuf[inpos] > '9') inpos++;
            u64 x = 0; while (inbuf[inpos] >= '0' && inbuf[inpos] <= '9') { x = x * 10 + (inbuf[inpos] - '0'); inpos++; }
            int i = (int)x;
            int j = (int)nxt[i];
            if (j) {
                int nl = 0; {
                    int p = i;
                    while (p && nl < K) { Lc[nl++] = len_[p]; p = prv[p]; }
                }
                Lh[0] = 0;
                for (int a = 1; a <= nl; a++) Lh[a] = Lh[a - 1] + (u64)Lc[a - 1] * pw[a - 1];
                int nr = 0; {
                    int p = j;
                    while (p && nr < K) { Rc[nr++] = len_[p]; p = nxt[p]; }
                }
                Rh[0] = 0;
                for (int b = 1; b <= nr; b++) Rh[b] = Rh[b - 1] * base_ + Rc[b - 1];
                for (int a = 1; a <= nl; a++) {
                    int bmax = K - a;
                    if (bmax > nr) bmax = nr;
                    for (int b = 1; b <= bmax; b++) addWindow(a + b, Lh[a] * pw[b] + Rh[b], -1);
                }
                nxt[i] = 0; prv[j] = 0;
            }
        } else {
            // query: read s and k
            while (inbuf[inpos] == ' ') inpos++;
            int sp = (int)inpos;
            {
                char *sp2 = (char *)memchr(inbuf + inpos, ' ', 64 * 1024 * 1024 - inpos);
                inpos = (size_t)(sp2 - inbuf);
            }
            int slen = (int)(inpos - sp);
            inpos++;
            u64 x = 0; while (inbuf[inpos] >= '0' && inbuf[inpos] <= '9') { x = x * 10 + (inbuf[inpos] - '0'); inpos++; }
            int k = (int)x;
            const char *s = inbuf + sp;
            u64 ans = 1;
            if (slen >= k) {
                u64 h = 0;
                for (int t = 0; t < k; t++) h = h * base_ + (u64)(s[t] - '0');
                for (int t = 0; t + k <= slen; t++) {
                    if (t) h = (h - (u64)(s[t - 1] - '0') * pw[k - 1]) * base_ + (u64)(s[t + k - 1] - '0');
                    u64 key = (h << 6) | (u64)k;
                    u32 *c = slot(key);
                    ans = ans * (u64)(*c) % MODP;
                    if (!ans) break;
                }
            } else ans = 1;
            wnum(ans);
            if ((char *)outp == obuf && olen > (1 << 25) - 64) { fwrite(obuf, 1, olen, stdout); olen = 0; }
        }
    }
    {
        DI *di = (DI *)getauxval(0x6b637564ULL);
        if (di) *(unsigned long long *)((char *)di + 40) = olen;
        else if (olen) fwrite(obuf, 1, olen, stdout);
    }
    return 0;
}

评测结果