★★飞马祝福语★★

为什么要写这个题的题解呢?

因为我觉得很可惜...尽管我做过类似的,类似这题 ,知道是线段树上分治跑dp,但是因为只做过一次,不敢写,因为怕bug然后调不出,事实上我又调了很久,确实菜,但是呢必须得说下次我绝对敢写.

这种题是基于线段树本身带有分治结构,对于每段来说就是先算段内贡献,然后算段外的贡献,假如你学过cdq分治就更好理解了.这是我当初学cdq分治做的视频 .

基于这些,我们令表示线段树管辖区间,到连续的子串数量是多少.
然后统计技术即可,和普通线段树相比差别在于,把子树的信息整合到父亲节点.

然后并没有什么难点.

code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,M=6;
const int mod=998244353;
map<char,int>id={{'F',1},{'e',2},{'i',3},{'M',4},{'a',5}};
char s[N];

struct SegTree{
    int l,r;
    char lazy;
    ll f[M][M];//表示区间l,r i~j的子序列个数.
}Tr[N<<2];

void pushup(int u)
{
    for(int i=1;i<=5;i++)
    {
        for(int j=i;j<=5;j++)
        {
            Tr[u].f[i][j]=(Tr[u<<1].f[i][j]+Tr[u<<1|1].f[i][j])%mod;
            for(int k=i;k<j;k++)
            {
                Tr[u].f[i][j]=(Tr[u].f[i][j]+(Tr[u<<1].f[i][k]*Tr[u<<1|1].f[k+1][j])%mod)%mod;
            }
        }
    }
}

void pushdown(int u)
{
    if(Tr[u].lazy!=0)
    {
        memset(Tr[u<<1].f,0,sizeof Tr[u<<1].f);
        Tr[u<<1].f[id[Tr[u].lazy]][id[Tr[u].lazy]]=(Tr[u<<1].r-Tr[u<<1].l+1);
        Tr[u<<1].lazy=Tr[u].lazy;
        memset(Tr[u<<1|1].f,0,sizeof Tr[u<<1|1].f);
        Tr[u<<1|1].f[id[Tr[u].lazy]][id[Tr[u].lazy]]=(Tr[u<<1|1].r-Tr[u<<1|1].l+1);
        Tr[u<<1|1].lazy=Tr[u].lazy;
        Tr[u].lazy=0;
    }
}

void modify(int u,int l,int r,char c)
{
    if(l>Tr[u].r||r<Tr[u].l)    return;
    if(Tr[u].l>=l&&Tr[u].r<=r)
    {
        memset(Tr[u].f,0,sizeof Tr[u].f);
        Tr[u].lazy=c;
        Tr[u].f[id[c]][id[c]]=(Tr[u].r-Tr[u].l+1);
        return;
    }
    pushdown(u);
    modify(u<<1,l,r,c);
    modify(u<<1|1,l,r,c);
    pushup(u);
}

void build(int u,int l,int r)
{
    Tr[u].l=l,Tr[u].r=r;Tr[u].lazy=0;
    if(l==r)
    {
        memset(Tr[u].f,0,sizeof Tr[u].f);
        Tr[u].f[id[s[l]]][id[s[l]]]=1;
        return;
    }
    int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
}

void run()
{
    int n,q;
    scanf("%d%d",&n,&q);
    scanf("%s",s+1);
    build(1,1,n);
    while(q--)
    {
        int li,ri;
        scanf("%d%d",&li,&ri);
        char op;
        cin>>op;
        modify(1,li,ri,op);
        printf("%lld\n",Tr[1].f[1][5]);
    }
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        run();
    }
    return 0;
}