代码

#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,
    MAXNODE = 13000000,
    MAXK = 50,
    MOD = 998244353
};

typedef struct {
    unsigned char byte[24];
} TrieNode;

static TrieNode trie[MAXNODE];
static int nodes = 1;
static int left_[MAXN], right_[MAXN];
static unsigned char color[MAXN];
#ifdef PROFILE
static u64 build_steps, query_steps;
#endif

static __attribute__((always_inline)) inline unsigned get24(const unsigned char *p) {
    return (*(const unsigned *)p) & 0xffffffU;
}

static __attribute__((always_inline)) inline void set24(unsigned char *p, unsigned v) {
    *(unsigned *)p = (*(unsigned *)p & 0xff000000U) | v;
}

static __attribute__((always_inline)) inline int get_child(int parent, int x) {
    return get24(trie[parent].byte + x * 3);
}

static __attribute__((always_inline)) inline int get_suffix(int node) {
    return get24(trie[node].byte + 18);
}

static __attribute__((always_inline)) inline int get_count(int node) {
    return get24(trie[node].byte + 21);
}

static int new_child(int parent, int x) {
    int g = nodes++;
    set24(trie[parent].byte + x * 3, g);
    if (parent) {
        int s = get_suffix(parent);
        int c = get_child(s, x);
        if (!c) c = new_child(s, x);
        set24(trie[g].byte + 18, c);
    }
    return g;
}

static __attribute__((always_inline)) inline void insert_single(int x) {
    int c = get_child(0, x);
    if (!c) c = new_child(0, x);
    set24(trie[c].byte + 21, get_count(c) + 1);
}

static int query_string(const char *s, int len, int k) {
    int node = 0;
    for (int i = 0; i + 1 < k; ++i) {
        node = get_child(node, (unsigned char)s[i] - '1');
        if (!node) return 0;
    }
    u64 ans = 1;
    for (int i = k - 1; i < len; ++i) {
#ifdef PROFILE
        ++query_steps;
#endif
        node = get_child(node, (unsigned char)s[i] - '1');
        if (!node) return 0;
        ans = ans * get_count(node) % MOD;
        if (!ans) return 0;
        node = get_suffix(node);
    }
    return (int)ans;
}

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

    int lef = x;
    for (int i = 2; left_[lef] && i < MAXK; ++i) lef = left_[lef];
    int node = get_child(0, color[lef]);
    int crossing = 0, crossing_len = 0;

    for (;;) {
        int i, t;
        if (crossing) {
            i = crossing_len--;
            t = y;
            node = crossing = get_suffix(crossing);
        } else {
            i = 1;
            t = right_[lef];
            if (lef == x) crossing = node;
        }
        for (; t && i < MAXK; ++i) {
#ifdef PROFILE
            ++build_steps;
#endif
            int c = get_child(node, color[t]);
            if (!c) c = new_child(node, color[t]);
            node = c;
            if (crossing) set24(trie[node].byte + 21,
                                get_count(node) + (joining ? 1 : -1));
            if (t == x) {
                crossing = node;
                crossing_len = i;
            }
            t = right_[t];
        }
        if (lef == x) break;
        lef = right_[lef];
    }

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

static void solve(DuckInfo *info) {
    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;
        insert_single(color[i]);
    }
    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);
    fprintf(stderr, "nodes=%d"
#ifdef PROFILE
            " build=%llu query=%llu"
#endif
            "\n", nodes
#ifdef PROFILE
            , build_steps, query_steps
#endif
    );
    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

评测结果