题解 (by;zjvarphi)
这种题的一个套路 (dp)，(dp_{i}=sum_{x}^{xin 字符集}dp_x+1)，(i) 为当前的字符。
发现可以矩乘优化，三种不同的字符对应三种不同的转移矩阵，用一个单点修改，区间查询线段树上维护即可。
最后再乘上一个初始矩阵，不要忘了空串也要算一个字符，但是不能算答案。
Code
#include<bits/stdc++.h>
#define ri signed
#define pd(i) ++i
#define bq(i) --i
#define func(x) std::function<x>
namespace IO{
char buf[1<<21],*p1=buf,*p2=buf;
#define gc() p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?(-1):*p1++
#define debug1(x) std::cerr << #x"=" << x << ' '
#define debug2(x) std::cerr << #x"=" << x << std::endl
#define Debug(x) assert(x)
struct nanfeng_stream{
template<typename T>inline nanfeng_stream &operator>>(T &x) {
bool f=false;x=0;char ch=gc();
while(!isdigit(ch)) f|=ch=='-',ch=gc();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=gc();
return x=f?-x:x,*this;
}
}cin;
}
using IO::cin;
namespace nanfeng{
#define FI FILE *IN
#define FO FILE *OUT
template<typename T>inline T cmax(T x,T y) {return x>y?x:y;}
template<typename T>inline T cmin(T x,T y) {return x>y?y:x;}
using ll=long long;
static const int N=1e5+7,MOD=998244353;
int n,m,opt,l,r,pos;
char s[N],ch[3];
struct Mat{
int a,b;
ll f[4][4];
Mat(){memset(f,0,sizeof(f));}
friend Mat operator*(const Mat &m1,const Mat &m2) {
Mat res;
for (ri i(0);i<=m1.a;pd(i))
for (ri j(0);j<=m2.b;pd(j)) {
for (ri k(0);k<=m1.b;pd(k)) {
res.f[i][j]+=m1.f[i][k]*m2.f[k][j]%MOD;
// if (i==0&&j==3) printf("f[%d][%d]=%lld f[%d][%d]=%lld
",i,k,m1.f[i][k],k,j,m2.f[k][j]);
}
res.f[i][j]%=MOD;
}
res.a=m1.a,res.b=m2.b;
return res;
}
}A,B,C,tmp,ad;
struct Seg{
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define up(x) T[x].sum=T[ls(x)].sum*T[rs(x)].sum
struct segmenttree{Mat sum;}T[N<<2];
func(void(int,int,int)) build=[&](int x,int l,int r) {
if (l==r) {
if (s[l]=='A') T[x].sum=A;
else if (s[l]=='B') T[x].sum=B;
else if (s[l]=='C') T[x].sum=C;
return;
}
int mid=(l+r)>>1;
build(ls(x),l,mid);
build(rs(x),mid+1,r);
up(x);
};
func(void(int,int,int,int)) update=[&](int x,int p,int l,int r) {
if (l==r) {
if (s[l]=='A') T[x].sum=A;
else if (s[l]=='B') T[x].sum=B;
else if (s[l]=='C') T[x].sum=C;
return;
}
int mid=(l+r)>>1;
if (p<=mid) update(ls(x),p,l,mid);
else update(rs(x),p,mid+1,r);
up(x);
};
func(Mat(int,int,int,int,int)) query=[&](int x,int l,int r,int lt,int rt) {
if (l<=lt&&rt<=r) return T[x].sum;
int mid=(lt+rt)>>1;
Mat res=tmp;
if (l<=mid) res=res*query(ls(x),l,r,lt,mid);
if (r>mid) res=res*query(rs(x),l,r,mid+1,rt);
return res;
};
}T;
inline int main() {
FI=freopen("string.in","r",stdin);
FO=freopen("string.out","w",stdout);
scanf("%d%d%s",&n,&m,s+1);
A.f[0][0]=B.f[0][0]=C.f[0][0]=1;
A.f[0][1]=B.f[0][2]=C.f[0][3]=1;
A.f[1][1]=A.f[2][1]=A.f[3][1]=A.f[2][2]=A.f[3][3]=1;
B.f[1][1]=B.f[1][2]=B.f[3][2]=B.f[2][2]=B.f[3][3]=1;
C.f[1][1]=C.f[1][3]=C.f[2][3]=C.f[2][2]=C.f[3][3]=1;
tmp.f[0][0]=tmp.f[1][1]=tmp.f[2][2]=tmp.f[3][3]=1;
ad.f[0][0]=1;
A.a=A.b=B.a=B.b=C.a=C.b=tmp.a=tmp.b=3;
ad.a=0,ad.b=3;
T.build(1,1,n);
for (ri i(1);i<=m;pd(i)) {
scanf("%d",&opt);
if (opt==1) {
scanf("%d%s",&pos,ch+1);
if (s[pos]!=ch[1]) {
s[pos]=ch[1];
T.update(1,pos,1,n);
}
} else {
scanf("%d%d",&l,&r);
Mat ans=T.query(1,l,r,1,n);
printf("%lld
",(ans.f[0][1]+ans.f[0][2]+ans.f[0][3])%MOD);
}
}
return 0;
}
}
int main() {return nanfeng::main();}