代码

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;

typedef long long i64;
typedef unsigned long long u64;

const int MAXN = 2e5, MAXK = 50, MAX_S_LEN = 1e7;
const u64 HASH_POW = 131, MUL_MOD = 998244353;

#ifdef WIN32
#define fread_unlocked fread
#define fwrite_unlocked fwrite
#endif

struct FastIO {
    char bufin[1<<27], bufout[1<<24];
    char *pin, *pout;
    FastIO() {
        fseek(stdin, 0, SEEK_END);
        int len = ftell(stdin);
        fseek(stdin, 0, SEEK_SET);
        fread_unlocked(bufin, sizeof(char), len, stdin);
        pin = bufin; pout = bufout;
    }
    
    inline char readch() { return *pin++; }
    
    inline void readstr(char *str) {
        char c=readch(); int p=0;
        while(!isalnum(c) && !ispunct(c)) c=readch();
        while(isalnum(c) || ispunct(c)) {
            str[p++]=c;
            c=readch();
        }
        str[p++]='\0';
    }
    
    template<typename T>
    inline void readint(T& x) {
        T f=1, r=0;
        while(!isdigit(*pin)) { if(*pin=='-')f=-1; pin++; }
        while(isdigit(*pin)) { r=r*10+*pin-'0'; pin++; }
        x = f*r;
    }
    
    template<typename T>
    inline void writeint(T x) {
        static char t[25], *pt; pt = t;
        if(x<0) { *pout++ = '-'; x = -x; }
        do {
            *pt++ = x%10 + '0'; x /= 10;
        } while(x);
        pt--;
        while(pt>=t) *pout++ = *pt--;
        *pout++ = '\n';
    }
    
    ~FastIO() {
        fwrite_unlocked(bufout, sizeof(char), pout - bufout, stdout);
    }
    
} fio;
#define readint fio.readint
#define writeint fio.writeint
#define readstr fio.readstr

struct Node {
    int ch;
    Node *prv, *nxt;
};

int n, m;
__gnu_pbds::gp_hash_table<u64, i64> cnt;
u64 hval[MAX_S_LEN + 10], powbase[MAX_S_LEN + 10];
int len;
char buf[MAX_S_LEN + 10];
Node nd[MAXN+10];

inline u64 calc_hash(u64 hval[], int l, int r) {
    return hval[r] - hval[l-1] * powbase[r-l+1];
}

void link(Node *x, Node *y) {
    int sz = 1, bnd = 1;
    static Node pit[MAXN+10];
    static u64 hval[MAXN+10];
    
    Node *p = x;
    x->nxt = y, y->prv = x;
    
    for(sz = 1; p->prv != NULL && sz <= MAXK-2; p = p->prv, sz++)
        ;
    
    for(int i = 1; p != NULL && i <= sz+MAXK-1; i++, bnd++, p = p->nxt) {
        pit[i] = *p;
        hval[i] = (hval[i-1] * HASH_POW + pit[i].ch);
    }
    --bnd;

    for(int i = 1; i <= sz; i++)
        for(int j = sz + 1; j <= min(bnd, i+MAXK-1); j++) {
            ++cnt[calc_hash(hval, i, j)];
            cnt[calc_hash(hval, i, j)] %= MUL_MOD;
        }
}

void split(Node *x, Node *y) {
    int sz = 1, bnd = 1;
    static Node pit[MAXN+10];
    static u64 hval[MAXN+10];
    
    Node *p = x;
    x->nxt = y, y->prv = x;
    
    for(sz = 1; p->prv != NULL && sz <= MAXK-2; p = p->prv, sz++)
        ;
    
    for(int i = 1; p != NULL && i <= sz+MAXK-1; i++, bnd++, p = p->nxt) {
        pit[i] = *p;
        hval[i] = (hval[i-1] * HASH_POW + pit[i].ch);
    }
    --bnd;

    for(int i = 1; i <= sz; i++)
        for(int j = sz + 1; j <= min(bnd, i+MAXK-1); j++) {
            --cnt[calc_hash(hval, i, j)];
            cnt[calc_hash(hval, i, j)] += MUL_MOD;
            cnt[calc_hash(hval, i, j)] %= MUL_MOD;
        }
    
    x->nxt = y->prv = NULL;
}

void init_hash() {
    powbase[0] = 1;
    for(int i = 1; i <= MAX_S_LEN; i++)
        powbase[i] = powbase[i-1] * HASH_POW;
}

int main() {
    init_hash();
    readint(n); readint(m);
    for(int i = 1; i <= n; i++) {
        readint(nd[i].ch);
        ++cnt[nd[i].ch];
    }
    
    while(m--) {
        int op, i, j, k;
        i64 ans = 1;
        
        readint(op);
        switch(op) {
            case 1:
                readint(i);
                readint(j);
                link(&nd[i], &nd[j]);
                break;
            case 2:
                readint(i);
                split(&nd[i], nd[i].nxt);
                break;
            case 3:
                readstr(buf+1);
                len = strlen(buf+1);
                readint(k);
                for(int i = 1; i <= len; i++)
                    hval[i] = (hval[i-1] * HASH_POW + (buf[i]-'0'));
                for(int i = 1; i <= len-k+1; i++)
                    ans = (ans * cnt[calc_hash(hval, i, i+k-1)]) % MUL_MOD;
                writeint(ans);
                break;
        }
    }
    return 0;
}

评测结果