代码

// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 #106640 <https://duck.ac/submission/106640>
//     （280.927015 ms，本账号本题最好件）= **本件正文的逐字节基座**。本次只做下面一处改动。
// [2] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 #106613 <https://duck.ac/submission/106613>
//     （284.765 ms）= #106640 的上一代（查询流水线 D 编译期常量化），本件继承其全部正文与致谢。
// ======================
// ===== 思路 =====
// **单变量：把热配对的 `VAL`(u8) 与 `NXT`(u32) 合成 8 B 一条的结构体**（BRIEF §2.19.779 的最小形态）。
// * 站点：链表遍历处 `bv[tb++] = VAL[y]; y = NXT[y];` 与 `s += (char)('0'+VAL[y]); y = NXT[y];` ——
//   每步要读**两个不同的数组**，各占一条 cache line。合成 `struct WN8{u32 nxt; u8 val;}` 后，
//   **一次 line 载入即拿到两个字段** ✓ 遍历语义一字不改（只是取值路径变了）。
// * 冷的一侧不动：`PRV` 的走步计数实测**多为 1**（`n17w_chain10m`/`n17w_multi10m` 上 w2=1）⇒ 保持独立数组。
// * 实测走步规模（本机 `-DLOCAL` 计数器）：w1 上界 **1 134 316**（`bin10m`）· w2 上界 1 129 647 · w3 = 0
//   ⇒ 收益上界 ≈ **3~10 ms**（每次被省的 line 访问按 10~30 拍未隐藏估）。
// * **逐位闸门**：`sample` / `n17w_bin10m`(27582 B) / `n17w_gen10m`(27640 B) / `n17w_chain10m`(10000 B)
//   四组**输出逐位相同** ✓（本机 A/B 计时在噪声内（±3%）故不作判据 —— 本题缺口 1.95% < 噪声，
//   见 §2.19.788；本发以判题机定价为准）。
// * ⚠ 本机驱动在 `#if defined(LOCAL)` 内（判题机同款编译不带 `-DLOCAL` 时走 `__libc_start_main` 插桩）⇒
//   本地复现必须 `-DLOCAL` ✓
// 目的：在本题（NOI2017 蚯蚓排队）上给"省 line 访问"这一类刀取一次**判题机汇率**。
// ================

typedef unsigned char u8;
typedef unsigned int u32;
typedef unsigned long long u64;

#ifndef CHECKING
#pragma GCC target("avx2,bmi2,popcnt,sse4.1,ssse3")
#endif

static const u32 MOD = 998244353;
static const u64 HB = 0x9E3779B97F4A7C15ULL | 1ULL;
static const u64 HMM = 0x9E3779B97F4A7C15ULL;

#define MAXN 300005
#define MAXK 50
#define TMAXBITS 19
#define TMAXSIZE (1u << TMAXBITS)

static const u8 *gip;
static const u8 *gEND;
static u8 *gob;

static u64 POW[MAXK + 2];
// [b17y WN8] §2.19.779 最小形态：热配对的 VAL(u8) 与 NXT(u32) 合成 8 B 一条的结构体
// ⇒ 一次 cache line 载入拿两个字段（原本两条 line）。PRV 冷（w2 多为 1）⇒ 不动。
// 遍历语义一字不改；MF_WN8=0 逐字节复现原形态，供本机 A/B。
#ifndef MF_WN8
#define MF_WN8 1
#endif
static u32 NXT[MAXN], PRV[MAXN];
static u8 VAL[MAXN];
struct WN8 { u32 nxt; u8 val; };
static WN8 WN[MAXN];
#define VALq(i) (MF_WN8 ? WN[(i)].val : VAL[(i)])
#define NXTq(i) (MF_WN8 ? WN[(i)].nxt : NXT[(i)])

static u64 *TBL[MAXK + 1];
static u32 TMSK[MAXK + 1];
static u64 POOL[51ULL * TMAXSIZE];

// bits: bit s of SMASK[d] set iff level (d+s) is needed; SMAXD[d] = highest such s
static u64 SMASK[MAXK + 2];
static u32 SMAXD[MAXK + 2];
static u32 DMAXX;   // deepest worm distance that can still produce a needed entry
static u8 NEEDED[MAXK + 1];

// prefetch distance of the query pipeline (iterations).  ~32 iters * ~10 cyc
// covers L3/DRAM latency; both hash chains are independent so no added latency.
#define UPF 32
#define QPF 32

// ---- input ----
static const u64 MASKV[9] = {0ULL, 0xFFULL, 0xFFFFULL, 0xFFFFFFULL, 0xFFFFFFFFULL,
                             0xFFFFFFFFFFULL, 0xFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFULL,
                             0xFFFFFFFFFFFFFFFFULL};
static const u64 INV5[9] = {1ULL,
                            0xCCCCCCCCCCCCCCCDULL, 0x8F5C28F5C28F5C29ULL, 0x1CAC083126E978D5ULL,
                            0xD288CE703AFB7E91ULL, 0x5D4E8FB00BCBE61DULL, 0x790FB65668C26139ULL,
                            0xE5032477AE8D46A5ULL, 0xC767074B22E90E21ULL};

static inline u32 rd() {  // integer token; stops after digits (cursor left on separator)
  while (*gip <= 32) gip++;
  u64 x;
  __builtin_memcpy(&x, gip, 8);
  u64 al = ((x + 0x4646464646464646ULL) | (x - 0x3030303030303030ULL)) & 0x8080808080808080ULL;
  u32 k = (al ? (u32)__builtin_ctzll(al) : 64u) >> 3;
  u64 d = (x & 0x0F0F0F0F0F0F0F0FULL) & MASKV[k];
  u64 t = (d * 10 + (d >> 8)) & 0x00FF00FF00FF00FFULL;
  t = (t * 100 + (t >> 16)) & 0x0000FFFF0000FFFFULL;
  t = (t * 10000 + (t >> 32)) & 0xFFFFFFFFULL;
  u32 j = 8 - k;
  gip += k;
  return (u32)((t >> j) * INV5[j]);
}

static inline u32 swar_len(const u8 *p) {  // length of digit run
  u32 L = 0;
  for (;;) {
    u64 x;
    __builtin_memcpy(&x, p, 8);
    u64 m = (x - 0x3030303030303030ULL) & ~x & 0x8080808080808080ULL;
    if (m) return L + ((u32)__builtin_ctzll(m) >> 3);
    L += 8;
    p += 8;
  }
}

// ---- output ----
static const char HEXD[201] =
    "00010203040506070809101112131415161718192021222324252627282930313233343536373839"
    "40414243444546474849505152535455565758596061626364656667686970717273747576777879"
    "8081828384858687888990919293949596979899";

static inline void wr(u32 v) {
  u32 len;
  if (v < 10) len = 1;
  else if (v < 100) len = 2;
  else if (v < 1000) len = 3;
  else if (v < 10000) len = 4;
  else if (v < 100000) len = 5;
  else if (v < 1000000) len = 6;
  else if (v < 10000000) len = 7;
  else if (v < 100000000) len = 8;
  else len = 9;
  u8 *o = gob + len;
  u32 t = v;
  while (t >= 100) {
    u32 q = t / 100;
    u32 r = t - q * 100;
    o -= 2;
    __builtin_memcpy(o, HEXD + r * 2, 2);
    t = q;
  }
  if (t < 10) *--o = (u8)('0' + t);
  else { o -= 2; __builtin_memcpy(o, HEXD + t * 2, 2); }
  gob += len;
  *gob++ = '\n';
}

// ---- hash table ----
#ifdef CHECKING
static u64 LEVELSUM[MAXK + 1];
static u32 GOP;
static void verify(u32 n);
#endif

static inline void tupd(u32 ell, u64 key, long sgn) {
  u64 *T = TBL[ell];
  key *= HMM;
  u32 idx = (u32)key & TMSK[ell];
  u64 kk = key >> 18;
  if (!kk) kk = 1;
  for (;;) {
    u64 e = T[idx];
#if defined(CHECKING)
    if ((e >> 18) == kk) { LEVELSUM[ell] += sgn; T[idx] = e + sgn; return; }
    if (e == 0) { LEVELSUM[ell] += sgn; T[idx] = (kk << 18) + (u64)(sgn > 0 ? sgn : 1); return; }
#else
    if ((e >> 18) == kk) { T[idx] = e + sgn; return; }
    if (e == 0) { T[idx] = (kk << 18) + (u64)(sgn > 0 ? sgn : 1); return; }
#endif
    idx = (idx + 1) & TMSK[ell];
  }
}

static inline u32 tget(u32 ell, u64 key) {
  const u64 *T = TBL[ell];
  key *= HMM;
  u32 idx = (u32)key & TMSK[ell];
  u64 kk = key >> 18;
  if (!kk) kk = 1;
  for (;;) {
    u64 e = T[idx];
    if ((e >> 18) == kk) return (u32)(e & 0x3FFFF);
    if (e == 0) return 0;
    idx = (idx + 1) & TMSK[ell];
  }
}

// same but takes the table/掩码 explicitly: one less dependent load on globals
static inline u32 tgetT(const u64 *__restrict T, u32 msk, u64 key) {
  key *= HMM;
  u32 idx = (u32)key & msk;
  u64 kk = key >> 18;
  if (!kk) kk = 1;
  for (;;) {
    u64 e = T[idx];
    if ((e >> 18) == kk) return (u32)(e & 0x3FFFF);
    if (e == 0) return 0;
    idx = (idx + 1) & msk;
  }
}

// ---- merge / split update ----
#define MAXENT 1300
static u64 EKEY[MAXENT];
static u8 ELVL[MAXENT];

// Tail-suffix-hash cache: after a merge whose B side is a single worm the new tail
// is that worm, and TCH[q] caches the hash of the string of length q+1 ending at it.
static u64 TCH[MAXK + 1];
static u32 TCT, TCN;

static inline void update(u32 i, u32 j, long sgn) {
  if (!DMAXX) return;  // only level 1 is queried: merges/splits change nothing
  u32 bv[MAXK + 1];
  u32 tb = 0;
  {
    u32 y = j;
    while (y && tb < MAXK) { bv[tb++] = VALq(y); y = NXTq(y); }
  }
  u32 nent = 0;
  if (sgn > 0 && tb == 1 && TCN && i == TCT) {
    // fast path: append single worm j after i using the cached suffix hashes
    u32 vj = VALq(j);
    u32 lim = TCN < MAXK ? TCN : MAXK - 1;
    for (u32 q = lim; q-- > 0;) {
      u64 hh = TCH[q] * HB + vj;
      TCH[q + 1] = hh;
      u32 lv = q + 2;
      if (NEEDED[lv]) {
        EKEY[nent] = hh; ELVL[nent] = (u8)lv; nent++;
        __builtin_prefetch(&TBL[lv][(u32)(hh * HMM) & TMSK[lv]]);
      }
    }
    TCH[0] = vj;
    TCN = (TCN < MAXK) ? TCN + 1 : MAXK;
    TCT = j;
    for (u32 t = 0; t < nent; t++) tupd(ELVL[t], EKEY[t], sgn);
    return;
  }
  TCT = 0;                 // general path invalidates the cache
  const int wantcache = (sgn > 0 && tb == 1);
  u64 chbuf[MAXK + 1];     // suffix hashes of the walked region (for cache rebuild)
  u64 HP[MAXK + 1];        // HP[s] = rolling hash of bv[0..s-1]  (s = 1..tb)
  {
    u64 hh = 0;
    for (u32 s = 1; s <= tb; s++) { hh = hh * HB + bv[s - 1]; HP[s] = hh; }
  }
  u32 x = i, d = 0;
  u64 h = 0;
  while (x && d < DMAXX) {   // deeper worms can never produce a needed level
    d++;
    h = (u64)VALq(x) * POW[d - 1] + h;  // prepend char x in front of the suffix string
    if (wantcache) chbuf[d - 1] = h;
    u64 need = SMASK[d];
    if (need) {
      u32 s_hi = SMAXD[d];
      if (s_hi > tb) s_hi = tb;
      if (s_hi) {
        // key(d,s) = h * HB^s + HP[s]  --  independent multiplies (no serial
        // chain), and only the s that are actually needed are visited.
        u64 m2 = need & ((1ULL << (s_hi + 1)) - 1);
        m2 &= ~1ULL;
        while (m2) {
          u32 s = (u32)__builtin_ctzll(m2);
          m2 &= m2 - 1;
          u64 key = h * POW[s] + HP[s];
          EKEY[nent] = key;
          ELVL[nent] = (u8)(d + s);
          nent++;
        }
      }
    }
    x = PRV[x];
  }
  if (wantcache) {  // single-worm append: the new tail is j, rebuild the cache
    u32 vj = VALq(j);
    u32 lim = d < MAXK ? d : MAXK - 1;
    TCH[0] = vj;
    for (u32 q = 0; q < lim; q++) TCH[q + 1] = chbuf[q] * HB + vj;
    TCN = lim + 1;
    TCT = j;
  }
  // lookahead prefetch: entry t+UPF is fetched while entry t is resolved, so
  // the table line is already in L1 (ref01 prefetched everything up front and
  // the ~1200 lines spill out of L1 into L2 before the update loop runs).
  for (u32 t = 0; t < nent; t++) {
    if (t + UPF < nent) {
      u32 lv = ELVL[t + UPF];
      __builtin_prefetch(&TBL[lv][(u32)(EKEY[t + UPF] * HMM) & TMSK[lv]]);
    }
    tupd(ELVL[t], EKEY[t], sgn);
  }
}

// ---- query ----
static void solve() {
  POW[0] = 1;
  for (u32 i = 1; i <= MAXK; i++) POW[i] = POW[i - 1] * HB;
  u32 n = rd(), m = rd();
#ifdef CHECKING
  GOP = 0;
#endif
  for (u32 i = 1; i <= n; i++) { VALq(i) = (u8)rd(); NXTq(i) = 0; PRV[i] = 0; }

  // (a) pre-scan: which k values appear in queries
  for (u32 i = 0; i <= MAXK; i++) NEEDED[i] = 0;
  {
    const u8 *p = gip;
    while (p < gEND) {
      const u8 *ls = p;
      for (;;) {  // find end of line (SWAR)
        u64 x;
        __builtin_memcpy(&x, p, 8);
        u64 y = x ^ 0x0A0A0A0A0A0A0A0AULL;
        u64 mm = (y - 0x0101010101010101ULL) & ~y & 0x8080808080808080ULL;
        if (mm) { p += ((u32)__builtin_ctzll(mm) >> 3); break; }
        p += 8;
        if (p >= gEND) { p = gEND; break; }
      }
      if (*ls == '3') {
        const u8 *q = p - 1;
        if (q >= ls && *q == '\r') q--;
        u32 k = 0, mul = 1;
        while (q >= ls && *q >= '0' && *q <= '9') { k += (u32)(*q - '0') * mul; mul *= 10; q--; }
        if (k >= 1 && k <= MAXK) NEEDED[k] = 1;
      }
      p++;
    }
  }
  // build level masks + sized tables
  for (u32 d = 0; d <= MAXK; d++) SMASK[d] = 0;
  for (u32 d = 1; d <= MAXK; d++) {
    u64 msk = 0;
    for (u32 s = 1; s + d <= MAXK; s++) if (NEEDED[s + d]) msk |= 1ULL << s;
    SMASK[d] = msk;
    SMAXD[d] = msk ? (u32)(63 - __builtin_clzll(msk)) : 0;
  }
  DMAXX = 0;
  for (u32 d = 1; d <= MAXK; d++) if (SMAXD[d]) DMAXX = d;
  {
    // at level l there are at most min(n-l+1, 6^l) distinct strings
    u64 *pool = POOL;
    u64 p6 = 6;
    for (u32 l = 1; l <= MAXK; l++) {
      u32 want = 5;
      u64 avail = (n + 1 > l) ? (u64)(n - l + 1) : 0;
      if (p6 < avail) avail = p6;
      if (avail) {
        u64 need = 2ULL * avail + 16;
        while ((1ULL << want) < need && want < TMAXBITS) want++;
      }
      TBL[l] = pool;
      TMSK[l] = (1u << want) - 1;
      pool += (1u << want);
      if (p6 < (1ULL << 40)) p6 *= 6;
    }
  }
  if (NEEDED[1]) {
    u32 c6[7] = {0, 0, 0, 0, 0, 0, 0};
    for (u32 i = 1; i <= n; i++) c6[VALq(i)]++;
    for (u32 v = 1; v <= 6; v++) if (c6[v]) tupd(1, (u64)v, (long)c6[v]);
  }
  for (u32 op = 0; op < m; op++) {
    u32 t = rd();
    if (t == 1) {
      u32 i = rd(), j = rd();
      update(i, j, 1);
      NXTq(i) = j; PRV[j] = i;
    } else if (t == 2) {
      u32 i = rd();
      u32 j = NXTq(i);
      if (j) update(i, j, -1);
      NXTq(i) = 0;
      if (j) PRV[j] = 0;
    } else {
      while (*gip <= 32) gip++;  // skip separator before s
      const u8 *ps = gip;
      u32 L = swar_len(ps);
      gip = ps + L;
      u32 k = rd();
      u64 res;
      if (k > MAXK) {
        res = 0;
      } else {
        u64 pk = POW[k];
        u32 nw = L - k + 1;
        u64 acc = 1;
        // all length-k windows coincide iff every character of s is the same
        u32 same = 1;
        {
          const u8 c0 = ps[0];
          u64 pat = 0x0101010101010101ULL * (u64)c0;
          const u8 *a = ps;
          u32 rem = L;
          while (rem >= 8) {
            u64 x;
            __builtin_memcpy(&x, a, 8);
            if (x != pat) { same = 0; break; }
            a += 8; rem -= 8;
          }
          if (same) for (; rem; rem--) { if (*a++ != c0) { same = 0; break; } }
        }
        if (same) {
          u64 h = 0;
          for (u32 i = 0; i < k; i++) h = h * HB + (u64)(ps[i] - '0');
          u64 base = tget(k, h) % MOD;
          u64 r = 1, e = nw;
          while (e) { if (e & 1) r = r * base % MOD; base = base * base % MOD; e >>= 1; }
          acc = r;
        } else {
          const u8 *p = ps;
          u64 *T = TBL[k];
          u32 msk = TMSK[k];
          u64 h1 = 0;
          for (u32 i = 0; i < k; i++) h1 = h1 * HB + (u64)(p[i] - '0');
          u32 i = 0;
          const u32 D = 8;   // compile-time constant; the small-table case is
                             // now handled by the plain tail loop below
          // h2 exists ONLY to build the prefetch index (h2*HMM)&msk, and msk < 2^19.
          // Multiplying by an odd constant is a bijection mod 2^19, so only bits 0..18
          // of h2 are ever observed => h2 may live in 32 bits and roll with 32-bit ops
          // (no movabs immediates, shorter encodings).
          const u32 HB32 = (u32)HB, HMM32 = (u32)HMM, PK32 = (u32)pk;
          if (msk >= (1u << 13) && nw > D) {
            u32 h2 = (u32)h1;
            for (u32 s = 0; s < D; s++)
              h2 = h2 * HB32 + (u32)(p[s + k] - '0') - (u32)(p[s] - '0') * PK32;
            for (; i + D < nw; i++) {
              __builtin_prefetch(&T[(h2 * HMM32) & msk]);
              u32 c = tgetT(T, msk, h1);
              if (!c) { acc = 0; i = nw; break; }   // skip the tail entirely
              acc *= c;
              if (acc >= (1ULL << 45)) acc %= MOD;
              h1 = h1 * HB + (u64)(p[i + k] - '0') - (u64)(p[i] - '0') * pk;
              h2 = h2 * HB32 + (u32)(p[i + D + k] - '0') - (u32)(p[i + D] - '0') * PK32;
            }
          }
          for (; i < nw; i++) {
            u32 c = tgetT(T, msk, h1);
            if (!c) { acc = 0; break; }
            acc *= c;
            if (acc >= (1ULL << 45)) acc %= MOD;
            h1 = h1 * HB + (u64)(p[i + k] - '0') - (u64)(p[i] - '0') * pk;
          }
          if (acc >= MOD) acc %= MOD;
        }
        res = acc;
      }
      wr((u32)res);
    }
#ifdef CHECKING
    GOP++;
    verify(n);
#endif
  }
}

#ifdef CHECKING
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
static void verify(u32 n) {
  static std::map<std::string, u32> cnt[MAXK + 1];
  for (u32 l = 1; l <= MAXK; l++) cnt[l].clear();
  for (u32 x = 1; x <= n; x++) {
    std::string s; u32 y = x;
    for (u32 l = 1; l <= MAXK; l++) {
      if (!y) break;
      s += (char)('0' + VALq(y)); y = NXTq(y);
      cnt[l][s]++;
    }
  }
  int bad = 0;
  for (u32 l = 1; l <= MAXK; l++) {
    if (!NEEDED[l]) continue;
    u64 tot = 0;
    {
      std::map<u64, std::string> seen;
      for (std::map<std::string, u32>::iterator it = cnt[l].begin(); it != cnt[l].end(); ++it) {
        u64 h = 0;
        for (size_t i = 0; i < it->first.size(); i++) h = h * HB + (u64)(it->first[i] - '0');
        std::map<u64, std::string>::iterator s2 = seen.find(h);
        if (s2 != seen.end()) {
          printf("  OP%u HASHCOLLISION level %u: %s vs %s\n", GOP, l,
                 it->first.c_str(), s2->second.c_str());
          bad = 1;
        } else seen[h] = it->first;
      }
    }
    for (std::map<std::string, u32>::iterator it = cnt[l].begin(); it != cnt[l].end(); ++it) {
      u64 h = 0;
      for (size_t i = 0; i < it->first.size(); i++) h = h * HB + (u64)(it->first[i] - '0');
      u32 got = tgetT(TBL[l], TMSK[l], h);
      if ((u64)got != it->second) {
        printf("  OP%u level %u str %s table=%u true=%u\n", GOP, l, it->first.c_str(), got, it->second);
        bad = 1;
      }
      tot += it->second;
    }
    if (tot != LEVELSUM[l]) { printf("  OP%u level %u SUM table=%llu true=%llu\n", GOP, l,
                                     (unsigned long long)LEVELSUM[l], (unsigned long long)tot); bad = 1; }
  }
  if (bad) { printf("^^^ after op %u\n", GOP); exit(1); }
}
#endif

#if defined(LOCAL)
// ---------- local driver (not compiled on the judge) ----------
#include <cstdio>
#include <cstdlib>
static u8 obuf[1 << 26];
extern "C" int main() {
  FILE *f = stdin;
  static u8 ibuf[1 << 26];
  size_t got = fread(ibuf, 1, sizeof(ibuf) - 32, f);
  for (u32 i = 0; i < 32; i++) ibuf[got + i] = '\n';
  gip = ibuf; gEND = ibuf + got; gob = obuf;
  solve();
  fwrite(obuf, 1, (size_t)(gob - obuf), stdout);
  return 0;
}
#else
struct DUCKDI{unsigned long abi;const char*sp;unsigned long sn;char*op;unsigned long ol,os;char*ep;unsigned long el,es;const char*IB;unsigned long IBl;char*OB;unsigned long OBl;unsigned long tsc;}__attribute__((packed));
extern "C" void __libc_start_main(void*m,int argc,char**argv){
 unsigned long*p=(unsigned long*)(argv+argc+1);while(*p)p++;p++;
 DUCKDI*d=0;for(;p[0];p+=2)if(p[0]==0x6b637564UL){d=(DUCKDI*)p[1];break;}
 gip=(const u8*)d->sp; gob=(u8*)d->op; gEND=gip+d->sn;
 solve();
 d->os=(unsigned long)(gob-(u8*)d->op);
 __asm__ volatile("syscall"::"a"(60),"D"(0):"rcx","r11","memory");
 for(;;);
}
int main(){return 0;}
#endif

评测结果