代码

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

const int SIZEN=1<<25;
char ss[SIZEN],*head,*tail,cc;int ll;
inline char Getchar(){
	if(head==tail){
		ll=fread(ss,1,SIZEN,stdin);
		tail=(head=ss)+ll;
	}
	return *head++;
}

inline void in(int &x){
	while(cc=Getchar(),cc<'!');x=cc-48;
	while(cc=Getchar(),cc>'!')x=x*10+cc-48;
}

inline void Getstr(int *a,int &len){
	while(cc=Getchar(),cc<'!');a[len=1]=cc-48;
	while(cc=Getchar(),cc>'!')a[++len]=cc-48;
}

typedef unsigned long long ULL;

struct HashMap{
    #define MOD ((1<<21)-1)
    ULL val[400010];
    int ne[400010], cnt[400010], tot, head[MOD+1];
    
    void insert(ULL v){
        int qwq=v&MOD;
        for(int i=head[qwq]; i; i=ne[i])
            if(val[i]==v){
                cnt[i]++;
                return;
            }
        val[++tot]=v;
        cnt[tot]=1;
        ne[tot]=head[qwq];
        head[qwq]=tot;
    }
    
    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]){
                    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;
    }
    #undef MOD
}H[65];

struct Node{
    Node *pre, *ne;
    int val;
}node[200010];

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

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{
        	int l;
			Getstr(s, l);
            in(K);
            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;
}

评测结果