代码

#ifndef DUCK_FASTIO_H
#define DUCK_FASTIO_H

typedef unsigned long duck_u64;
typedef long duck_i64;

typedef struct {
    duck_u64 abi_version;
    const char *stdin_ptr;
    duck_u64 stdin_size;
    char *stdout_ptr;
    duck_u64 stdout_limit;
    duck_u64 stdout_size;
    char *stderr_ptr;
    duck_u64 stderr_limit;
    duck_u64 stderr_size;
    const char *ib_ptr;
    duck_u64 ib_limit;
    char *ob_ptr;
    duck_u64 ob_limit;
    duck_u64 tsc_frequency;
} __attribute__((packed)) DuckInfo;

static __attribute__((always_inline)) inline DuckInfo *duck_info(long argc, char **argv) {
    char **p = argv + argc + 1;
    while (*p) ++p;
    duck_u64 *aux = (duck_u64 *)(p + 1);
    while (aux[0]) {
        if (aux[0] == 0x6b637564UL) return (DuckInfo *)aux[1];
        aux += 2;
    }
    return (DuckInfo *)0;
}

static __attribute__((always_inline)) inline duck_u64 duck_read_u64(const char **cursor) {
    const char *p = *cursor;
    while ((unsigned char)(*p - '0') > 9) ++p;
    duck_u64 value = 0;
    do {
        value = value * 10 + (unsigned char)(*p - '0');
        ++p;
    } while ((unsigned char)(*p - '0') <= 9);
    *cursor = p;
    return value;
}

static __attribute__((always_inline)) inline duck_i64 duck_read_i64(const char **cursor) {
    const char *p = *cursor;
    while (*p != '-' && (unsigned char)(*p - '0') > 9) ++p;
    int negative = *p == '-';
    p += negative;
    duck_u64 value = 0;
    do {
        value = value * 10 + (unsigned char)(*p - '0');
        ++p;
    } while ((unsigned char)(*p - '0') <= 9);
    *cursor = p;
    return negative ? -(duck_i64)value : (duck_i64)value;
}

static __attribute__((always_inline)) inline char *duck_write_u64(char *out, duck_u64 value) {
    char tmp[24];
    unsigned n = 0;
    do {
        tmp[n++] = (char)('0' + value % 10);
        value /= 10;
    } while (value);
    do *out++ = tmp[--n]; while (n);
    return out;
}

static __attribute__((always_inline)) inline char *duck_write_i64(char *out, duck_i64 value) {
    if (value < 0) {
        *out++ = '-';
        return duck_write_u64(out, (duck_u64)(-value));
    }
    return duck_write_u64(out, (duck_u64)value);
}

static __attribute__((always_inline, noreturn)) inline void duck_exit(void) {
    __asm__ volatile("mov $60,%%eax;xor %%edi,%%edi;syscall" ::: "rax", "rdi", "rcx", "r11", "memory");
    __builtin_unreachable();
}

#endif


typedef unsigned long long u64;
enum { MAXN = 200005, HLOG = 23, HSIZE = 1 << HLOG, HMASK = HSIZE - 1,
       MOD = 998244353, BASE = 1000003 };

static int left_[MAXN], right_[MAXN];
static unsigned char color[MAXN];
static u64 table_key[HSIZE];
static int table_count[HSIZE];
static u64 power_[51], salt[51];

static __attribute__((always_inline)) inline unsigned locate(u64 hash, int len) {
    u64 key = hash ^ salt[len];
    if (!key) key = 1;
    unsigned p = key * 11400714819323198485ULL >> (64 - HLOG);
    while (table_key[p] && table_key[p] != key) p = (p + 1) & HMASK;
    if (!table_key[p]) table_key[p] = key;
    return p;
}

static __attribute__((always_inline)) inline void change(u64 hash, int len, int delta) {
    unsigned p = locate(hash, len);
    table_count[p] += delta;
}

static __attribute__((always_inline)) inline int get(u64 hash, int len) {
    unsigned p = locate(hash, len);
    return table_count[p];
}

static void modify_link(int x, int y) {
    int joining = y != 0;
    if (!joining) y = right_[x];

    unsigned char buf[100], rev[50];
    int nl = 0, nr = 0;
    for (int p = x; p && nl < 49; p = left_[p]) rev[nl++] = color[p];
    for (int i = 0; i < nl; ++i) buf[i] = rev[nl - 1 - i];
    for (int p = y; p && nr < 49; p = right_[p]) buf[nl + nr++] = color[p];
    int all = nl + nr;
    u64 pref[100];
    pref[0] = 0;
    for (int i = 0; i < all; ++i) pref[i + 1] = pref[i] * BASE + buf[i] + 1;
    for (int len = 2; len <= 50 && len <= all; ++len) {
        int first = nl - len + 1;
        if (first < 0) first = 0;
        int last = nl - 1;
        if (last > all - len) last = all - len;
        for (int s = first; s <= last; ++s)
            change(pref[s + len] - pref[s] * power_[len], len, joining ? 1 : -1);
    }

    if (joining) {
        right_[x] = y;
        left_[y] = x;
    } else {
        right_[x] = 0;
        left_[y] = 0;
    }
}

static int query_string(const char *s, int len, int k) {
    u64 h = 0;
    for (int i = 0; i < k; ++i) h = h * BASE + (unsigned char)s[i] - '0';
    u64 ans = 1;
    int c = get(h, k);
    if (!c) return 0;
    ans = c;
    for (int i = k; i < len; ++i) {
        h = (h - ((unsigned char)s[i - k] - '0') * power_[k - 1]) * BASE
            + (unsigned char)s[i] - '0';
        c = get(h, k);
        if (!c) return 0;
        ans = ans * (unsigned)c % MOD;
        if (!ans) return 0;
    }
    return (int)ans;
}

static void solve(DuckInfo *info) {
    power_[0] = 1;
    for (int i = 1; i <= 50; ++i) power_[i] = power_[i - 1] * BASE;
    for (int i = 1; i <= 50; ++i) salt[i] = 0x9e3779b97f4a7c15ULL * i;
    const char *p = info->stdin_ptr;
    int n = duck_read_u64(&p);
    int m = duck_read_u64(&p);
    for (int i = 1; i <= n; ++i) {
        color[i] = (unsigned char)duck_read_u64(&p) - 1;
        change(color[i] + 1, 1, 1);
    }
    char *out = info->stdout_ptr;
    while (m--) {
        int op = duck_read_u64(&p);
        if (op == 1) {
            int x = duck_read_u64(&p);
            int y = duck_read_u64(&p);
            modify_link(x, y);
        } else if (op == 2) {
            modify_link(duck_read_u64(&p), 0);
        } else {
            while (*p <= ' ') ++p;
            const char *s = p;
            while (*p > ' ') ++p;
            int len = p - s;
            int k = duck_read_u64(&p);
            out = duck_write_u64(out, query_string(s, len, k));
            *out++ = '\n';
        }
    }
    info->stdout_size = out - info->stdout_ptr;
}

#ifdef LOCAL
#include <stdio.h>
int main(void) {
    static char in[50000000], out[5000000];
    DuckInfo info = {0};
    info.stdin_size = fread(in, 1, sizeof in, stdin);
    info.stdin_ptr = in;
    info.stdout_ptr = out;
    solve(&info);
    fwrite(out, 1, info.stdout_size, stdout);
}
#else
__attribute__((noreturn)) void __libc_start_main(void *x, long n, char **v) {
    DuckInfo *info = duck_info(n, v);
    solve(info);
    duck_exit();
}
int main(void) {}
#endif

评测结果