代码

// NOI2017 Day1 T2 -- 蚯蚓排队 (Earthworm queue)
// Counts of backwards strings of each length 1..50 kept in open-addressing tables.
//   merge : for x within last 49 of A, add strings (suffix of A at x)+(prefix of B), lengths d+1..min(50,d+|B|)
//   split : same computation, decrement
//   query : multiply counts of every length-k substring of s
// Optimisations:  (a) pre-scan finds which k values occur -> only those levels are maintained,
//                (b) per-level tables are sized to 2*(n-l+1) slots, packed in one pool,
//                (c) entry generation is batched and prefetched before the (latency bound) updates.
typedef unsigned char u8;
typedef unsigned int u32;
typedef unsigned long long u64;

static const u32 MOD = 998244353;
static const u64 HB = 0x9E3779B97F4A7C15ULL | 1ULL;
// hash must be mixed before splitting into index/key: key = hash>>18 alone would
// make strings differing in the last character (e.g. "12321" vs "12322") collide.
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];
static u32 NXT[MAXN], PRV[MAXN];
static u8 VAL[MAXN];

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];

// ---- 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() {
  // RIGHT-ALIGN the k digits by shifting t LEFT 8*(8-k) bits: the separator byte (t's
  // byte k) and everything after it shifts out of the 64-bit word, so the three-level
  // SWAR fusion then yields the value DIRECTLY -- no MASKV[]/INV5[] table loads, no >>j,
  // no in-table magic multiply.  Ported verbatim from work/noip17f_lane4/PF2.cpp rd()
  // (lines 43-62), where it is the shipped, row-minimum form.
  for (;;) {
    u64 x;
    __builtin_memcpy(&x, gip, 8);
    u64 t = x ^ 0x3030303030303030ULL;
    u64 mm = ((t + 0x7676767676767676ULL) | t) & 0x8080808080808080ULL;
    u32 k = mm ? (u32)(__builtin_ctzll(mm) >> 3) : 8u;
    if (k == 0) { gip++; continue; }
    u64 d = t << ((8u - k) << 3);
    u64 c1 = (d * 10 + (d >> 8)) & 0x00FF00FF00FF00FFULL;
    u64 c2 = (c1 * 100 + (c1 >> 16)) & 0x0000FFFF0000FFFFULL;
    u64 c3 = (c2 * 10000 + (c2 >> 32));
    gip += k + 1;
    return (u32)c3;
  }
}

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];
  }
}

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

#ifdef PROF
static u64 T_UPD, T_QRY, T_PRE, T_PARSE, T_BUF;
static u32 N_UPD, N_QRY, N_ENT;
static inline u64 rdtp(){ unsigned a,d; __asm__ volatile("rdtsc":"=a"(a),"=d"(d)); return ((u64)d<<32)|a; }
#else
#define rdtp() 0
#endif

// 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.
// This removes the dependent PRV pointer walk for the very common "append one worm"
// pattern.  Invalidated by any split or by any multi-worm merge.
static u64 TCH[MAXK + 1];
static u32 TCT, TCN;

static inline void update(u32 i, u32 j, long sgn) {
#ifdef PROF
  u64 _t0 = rdtp(); N_UPD++;
#endif
  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++] = VAL[y]; y = NXT[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 = VAL[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]) {
        { u64 _k = hh * HMM; u64 _g = _k >> 18; if (!_g) _g = 1; ESLOT[nent] = &TBL[lv][(u32)_k & TMSK[lv]]; ETAG[nent] = _g; EKEY[nent] = hh; ELVL[nent] = (u8)lv; nent++; }
        ;
      }
    }
    TCH[0] = vj;
    TCN = (TCN < MAXK) ? TCN + 1 : MAXK;
    TCT = j;
#ifdef PROF
    T_BUF += rdtp() - _t0; N_ENT += nent; _t0 = rdtp();
#endif
    { for (u32 _c = 0; _c < nent; _c += 32) { u32 _hi = _c + 32; if (_hi > nent) _hi = nent; for (u32 _u = _c; _u < _hi; _u++) __builtin_prefetch(ESLOT[_u]); for (u32 _u = _c; _u < _hi; _u++) { u64 *_T = ESLOT[_u]; u64 _g = ETAG[_u]; u64 _e = *_T; if ((_e >> 18) == _g) { *_T = _e + sgn; continue; } if (_e == 0) { *_T = (_g << 18) + (u64)(sgn > 0 ? sgn : 1); continue; } tupd(ELVL[_u], EKEY[_u], sgn); } } }
#ifdef PROF
    T_UPD += rdtp() - _t0;
#endif
    return;
  }
  TCT = 0;                 // general path invalidates the cache
  u64 chbuf[MAXK + 1];     // suffix hashes of the walked region (for cache rebuild)
  u32 x = i, d = 0;
  u64 h = 0;
  while (x && d < DMAXX) {   // deeper worms can never produce a needed level
    d++;
    h = (u64)VAL[x] * POW[d - 1] + h;  // prepend char x in front of the suffix string
    chbuf[d - 1] = h;
    u32 s_hi = SMAXD[d];
    if (s_hi) {
      if (s_hi > tb) s_hi = tb;
      if (s_hi) {
        u64 need = SMASK[d];
        u64 key = h;
        for (u32 s = 1; s <= s_hi; s++) {
          key = key * HB + bv[s - 1];
          if ((need >> s) & 1) {
            { u64 _k = key * HMM; u64 _g = _k >> 18; if (!_g) _g = 1;
            ESLOT[nent] = &TBL[d + s][(u32)_k & TMSK[d + s]]; ETAG[nent] = _g;
            EKEY[nent] = key; ELVL[nent] = (u8)(d + s); nent++; }
            ;
          }
        }
      }
    }
    x = PRV[x];
  }
  if (sgn > 0 && tb == 1) {  // single-worm append: the new tail is j, rebuild the cache
    u32 vj = VAL[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;
  }
#ifdef PROF
  T_BUF += rdtp() - _t0; N_ENT += nent; _t0 = rdtp();
#endif
  { for (u32 _c = 0; _c < nent; _c += 32) { u32 _hi = _c + 32; if (_hi > nent) _hi = nent; for (u32 _u = _c; _u < _hi; _u++) __builtin_prefetch(ESLOT[_u]); for (u32 _u = _c; _u < _hi; _u++) { u64 *_T = ESLOT[_u]; u64 _g = ETAG[_u]; u64 _e = *_T; if ((_e >> 18) == _g) { *_T = _e + sgn; continue; } if (_e == 0) { *_T = (_g << 18) + (u64)(sgn > 0 ? sgn : 1); continue; } tupd(ELVL[_u], EKEY[_u], sgn); } } }
#ifdef PROF
  T_UPD += rdtp() - _t0;
#endif
}

// ---- 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++) { VAL[i] = (u8)rd(); NXT[i] = 0; PRV[i] = 0; }

  // (a) pre-scan: which k values appear in queries
  for (u32 i = 0; i <= MAXK; i++) NEEDED[i] = 0;
#ifdef PROF
  u64 _p0 = rdtp();
#endif
  {
    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++;
    }
  }
#ifdef PROF
  T_PRE = rdtp() - _p0;
#endif
  // 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, so the table
    // only needs twice that many slots (level 1 -> 32 slots, stays in L1)
    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[VAL[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);
      NXT[i] = j; PRV[j] = i;
    } else if (t == 2) {
      u32 i = rd();
      u32 j = NXT[i];
      if (j) update(i, j, -1);
      NXT[i] = 0;
      if (j) PRV[j] = 0;
    } else {
#ifdef PROF
      N_QRY++; u64 _q0 = rdtp();
#endif
      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;  // no worm has a string longer than 50
      } 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
        // (holds for the "all ones" test points) -> single lookup + power
        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 h1 = 0;
          for (u32 i = 0; i < k; i++) h1 = h1 * HB + (u64)(p[i] - '0');
          u32 i = 0;
          const u32 D = (TMSK[k] < (1u << 13)) ? 0 : 8;  // pipeline only for big tables
          if (nw > D) {
            u64 h2 = h1;
            u64 *T = TBL[k];
            u32 msk = TMSK[k];
            for (u32 j = 0; j < D; j++)
              h2 = h2 * HB + (u64)(p[j + k] - '0') - (u64)(p[j] - '0') * pk;
            for (; i + D < nw; i++) {
              __builtin_prefetch(&T[(u32)(h2 * HMM) & msk]);
              u32 c = tget(k, 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;
              h2 = h2 * HB + (u64)(p[i + D + k] - '0') - (u64)(p[i + D] - '0') * pk;
            }
          }
          for (; i < nw; i++) {
            u32 c = tget(k, 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 PROF
      T_QRY += rdtp() - _q0;
#endif
    }
#ifdef CHECKING
    GOP++;
#ifdef CHECKALL
    verify(n);
#else
    if (op + 1 == m) verify(n);
#endif
#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' + VAL[y]); y = NXT[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 = tget(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

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;}

评测结果