题目概述

Karshilov's Matching Problem

解题报告

首先不难想到对 $n$ 个匹配串建AC自动机，在 $fail$ 树上求和就可以得知匹配到 $p$ 点时的权值和。

然后我们观察一下操作的形式，询问只询问前缀，而修改只修改后缀，因此我们有个暴力的想法：维护前 $i$ 个字符的信息，包括匹配到自动机的哪个位置，以及前面的匹配权值和。询问时直接查询第 $l$ 个位置的信息，修改时把后 $l$ 个位置更新成 $c$ 字符。

在修改后，后 $l$ 个位置都是 $c$ 字符，因此会在自动机上不停的沿 $c$ 字符匹配，显然这个过程可以用倍增来节约时间。因此我们可以把连续一段相同字符缩成一个线段，查询时在这个线段上倍增查询，而修改时就非常简单了，找到对应的线段 $i$ ，把 $i$ 拆成两部分，$n-l+1$ 后面的部分直接删去，然后新增一个 $[n-l+1,n]$ 的线段，更新一下信息就行了。

复杂度 $O(10n\log_2m+m\log_2m)$ 。

示例程序

#include<cstdio>
#include<cctype>
using namespace std;
const int maxl=100000,maxn=300000,LOG=18,MOD=998244353;

int m,n,te;char t[maxl+5],s[maxn+5];
int pl,son[maxl+5][10],fai[maxl+5];
int que[maxl+5],val[maxl+5];
int ST[10][maxl+5][LOG+1],sum[10][maxl+5][LOG+1];
struct giao {int w,L,R,S,pre;};
int K;giao a[maxn+5];

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
int reads(char *s){
    int len=0;char ch=readc();
    while (!isdigit(ch)) ch=readc();
    while (isdigit(ch)) s[++len]=ch,ch=readc();
    s[len+1]=0;return len;
}
#define ADD(x,y) (((x)+(y))%MOD)
void Insert(char *s,int w){
    int p=0;
    for (int i=1;s[i];i++){
        int w=s[i]-'0',&u=son[p][w];
        if (!u) u=++pl;p=u;
    }
    val[p]=ADD(val[p],w);
}
void getfai(){
    int Head=0,Tail=0;
    for (int i=0,u;i<10;i++)
        if (u=son[0][i]) fai[u]=0,que[++Tail]=u; else son[0][i]=0;
    while (Head!=Tail)
        for (int x=que[++Head],i=0,u;i<10;i++)
            if (u=son[x][i]) fai[u]=son[fai[x]][i],val[u]=ADD(val[u],val[fai[u]]),que[++Tail]=u;
            else son[x][i]=son[fai[x]][i];
    for (int i=0;i<10;i++){
        for (int x=0;x<=pl;x++) ST[i][x][0]=son[x][i],sum[i][x][0]=val[son[x][i]];
        for (int j=1;j<=LOG;j++)
            for (int x=0;x<=pl;x++)
                ST[i][x][j]=ST[i][ST[i][x][j-1]][j-1],
                sum[i][x][j]=ADD(sum[i][x][j-1],sum[i][ST[i][x][j-1]][j-1]);
    }
}
int Ask(int x){
    int L=1,R=K;
    for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
        x>=a[mid].L?L=mid+1:R=mid-1;
    int ans=a[R].pre,cnt=x-a[R].L+1,w=a[R].w,S=a[R].S;
    for (int j=LOG;~j;j--)
        if (cnt>>j&1) ans=ADD(ans,sum[w][S][j]),S=ST[w][S][j];
    return ans;
}
void Update(int x,int c){
    int L=1,R=K;
    for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
        x>=a[mid].L?L=mid+1:R=mid-1;
    if (x==a[R].L) K=R,a[K].w=c,a[K].L=x,a[K].R=n; else {
        a[R].R=x-1;
        int ans=a[R].pre,cnt=a[R].R-a[R].L+1,w=a[R].w,S=a[R].S;
        for (int j=LOG;~j;j--)
            if (cnt>>j&1) ans=ADD(ans,sum[w][S][j]),S=ST[w][S][j];
        K=R+1;
        a[K].w=c;a[K].L=x;a[K].R=n;a[K].S=S;a[K].pre=ans;
    }
}
int main(){
    readi(m);
    for (int i=1,w;i<=m;i++){
        reads(t);readi(w);
        Insert(t,w);
    }
    getfai();
    n=reads(s);K=n;
    a[1]=(giao){s[1]-'0',1,1,0,0};
    for (int i=2;i<=n;i++){
        a[i].w=s[i]-'0';a[i].L=a[i].R=i;
        a[i].S=son[a[i-1].S][a[i-1].w];
        a[i].pre=ADD(a[i-1].pre,val[a[i].S]);
    }
    for (readi(te);te;te--){
        int tp,x,y;
        readi(tp);readi(x);
        if (tp==2) printf("%d\n",Ask(x));
        else readi(y),Update(n-x+1,y);
    }
    return 0;
}