代码

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>

template <typename T> void in(T &_){
    char c=getchar(); _=0; int fl=1;
    while(c<'0'||c>'9') fl=c=='-'?-1:fl, c=getchar();
    while(c>='0'&&c<='9') _=_*10+c-'0', c=getchar(); _*=fl;
}

typedef unsigned long long ULL;

struct HashMap{
    #define MOD ((1<<21)-1)
    ULL val[200010];
    int ne[200010], cnt[200010], tot, head[MOD+1];
    std::queue<int> q;
    
    void insert(ULL v){
        int qwq=v%MOD;
        for(int i=head[qwq]; i; i=ne[i])
            if(val[i]==v){
                cnt[i]++;
                return;
            }
        int now;
        if(q.empty()) now=++tot;
        else{now=q.front(); q.pop();}
        val[now]=v;
        cnt[now]=1;
        ne[now]=head[qwq];
        head[qwq]=now;
    }
    
    void erase(ULL v){
        int qwq=v%MOD;
        for(int i=head[qwq], j=-1; i; j=i, i=ne[i])
            if(val[i]==v){
                cnt[i]--;
                if(!cnt[i]){
                    q.push(i);
                    if(~j) ne[j]=ne[i];
                    else head[qwq]=ne[i];
                }
                return;
            }
    }
    
    int count(ULL v){
        int qwq=v%MOD;
        for(int i=head[qwq]; i; i=ne[i])
            if(val[i]==v) return cnt[i];
        return 0;
    }
    
    void print(){
        for(int i=1; i<=tot; i++) printf(" %llu %d\n", val[i], cnt[i]);
    }
    #undef MOD
}H[65];

struct Node{
    Node *pre, *ne;
    int val;
    Node() : pre(NULL), ne(NULL){}
}node[200010];

const int MOD=998244353, MAX_K=55;
ULL bin[MAX_K+10];
int N, M, s[10000010], f[2*MAX_K+5];
char _s[10000010];

namespace Hash{
    ULL h[10000010];
    
    void init(int *s, int l, int r){
        h[l-1]=1;
        for(int i=l; i<=r; i++) h[i]=h[i-1]*7+s[i];
    }
    
    ULL query(int l, int r){return h[r]-h[l-1]*bin[r-l+1];}
}

int main(){
    int opt, x, y, K;
    in(N); in(M);
    bin[0]=1;
    for(int i=1; i<=MAX_K; i++) bin[i]=bin[i-1]*7;
    for(int i=1; i<=N; i++){
        in(node[i].val);
        H[1].insert(node[i].val);
    }
    while(M--){
        in(opt);
        if(opt==1){
            in(x); in(y);
            int L=MAX_K+1, R=MAX_K;
            Node *v=node+x;
            while(L>1 && v) f[--L]=v->val, v=v->pre;
            v=node+y;
            while(R<2*MAX_K && v) f[++R]=v->val, v=v->ne;
            Hash::init(f, L, R);
            for(int i=L; i<=MAX_K; i++)
                for(int j=MAX_K+1; j<=std::min(R, i+49); j++)
                    H[j-i+1].insert(Hash::query(i, j));
            node[x].ne=node+y; node[y].pre=node+x;
        }else if(opt==2){
            in(x);
            int L=MAX_K+1, R=MAX_K;
            Node *v=node+x;
            while(L>1 && v) f[--L]=v->val, v=v->pre;
            v=node+x; v=v->ne;
            while(R<2*MAX_K && v) f[++R]=v->val, v=v->ne;
            Hash::init(f, L, R);
            for(int i=L; i<=MAX_K; i++)
                for(int j=MAX_K+1; j<=std::min(R, i+49); j++) 
                    H[j-i+1].erase(Hash::query(i, j));
            node[x].ne->pre=NULL; node[x].ne=NULL;
        }else{
            scanf("%s", _s+1);
            in(K); int l=strlen(_s+1);
            for(int i=1; i<=l; i++) s[i]=_s[i]-'0';
            int ans=1;
            Hash::init(s, 1, l);
            for(int i=K; i<=l; i++)
                ans=1LL*ans*H[K].count(Hash::query(i-K+1, i))%MOD;
            printf("%d\n", ans);
        }
    }
    return 0;
}

评测结果