题解

解题思路：
res[i,j]表示i开头j结尾的子串个数,这个倒着做遍前缀和就行
然后考虑一次询问的答案就是res[a,b],再考虑修改会造成什么影响,不难发现就是减少修改前的字母,增加修改后的字母
于是对于所有26个字母,用线段树统计他前面有多少个,后面有多少个然后把贡献减掉
(注意如果i=j会多减一次,所以还要再加回来)
然后修改完的字母再做一次逆操作即可

代码如下:

#include<bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
constexpr long long N=100005; 
using namespace std; 
long long T=1; 
long long n,q; 
long long res[30][30],sum[30][N]; 
string s; 
struct sgt{ 
    long long tr[N<<2]; 
    void pushup(long long u){ 
        tr[u]=tr[u<<1]+tr[u<<1|1]; 
    } 
    void build(long long u,long long l,long long r,char c){ 
        if (l==r){ 
            tr[u]=(s[l]==c); 
            return; 
        } 
        long long mid=l+r>>1; 
        build(u<<1,l,mid,c); 
        build(u<<1|1,mid+1,r,c); 
        pushup(u); 
    } 
    void modify(long long u, long long l, long long r, long long p, long long v){ 
        if (l==r){ 
            tr[u]+=v; 
            return; 
        } 
        long long mid=l+r>>1; 
        if (p<=mid)modify(u<<1,l,mid,p,v); 
        else modify(u<<1|1,mid+1,r,p,v); 
        pushup(u); 
    } 
    long long qry(long long u,long long l,long long r,long long L,long long R){ 
        if(l>=L&&r<=R)return tr[u]; 
        long long mid=l+r>>1; 
        long long res=0; 
        if(L<=mid)res+=qry(u<<1,l,mid,L,R); 
        if(R>mid)res+=qry(u<<1|1,mid+1,r,L,R); 
        return res; 
    } 
} 
g[30]; 
void solve(long long cs){ 
    cin>>n>>q>>s; 
    s=" "+s; 
    for(long long i=n;i;i--){ 
        for(char c='a';c<='z';c++){ 
            sum[c-'a'][i]=sum[c-'a'][i+1]+(s[i]==c); 
        } 
    } 
    set<long long>t[30]; 
    for(long long i=1;i<=n;i++){ 
        for(char c='a';c<='z';c++){ 
            res[s[i]-'a'][c-'a']+=sum[c-'a'][i]; 
        } 
    } 
    for(char c='a';c<='z';c++){ 
        g[c-'a'].build(1,1,n,c); 
    } 
    while(q--){ 
        long long op; 
        cin>>op; 
        if(op==1){ 
            long long p; 
            char c; 
            cin>>p>>c; 
            for(char x='a';x<='z';x++){ 
                res[s[p]-'a'][x-'a']-=g[x-'a'].qry(1,1,n,p,n); 
                res[x-'a'][s[p]-'a']-=g[x-'a'].qry(1,1,n,1,p); 
                if(x==s[p])res[x-'a'][s[p]-'a']++; 
            } 
            g[s[p]-'a'].modify(1,1,n,p,-1); 
            s[p]=c; 
            g[s[p]-'a'].modify(1,1,n,p,1); 
            for(char x='a';x<='z';x++){ 
                res[s[p]-'a'][x-'a']+=g[x-'a'].qry(1,1,n,p,n); 
                res[x-'a'][s[p]-'a']+=g[x-'a'].qry(1,1,n,1,p); 
                if(x==s[p])res[x-'a'][s[p]-'a']--; 
            } 
        }else{ 
            char x,y; 
            cin>>x>>y; 
            cout<<res[x-'a'][y-'a']<<'\n'; 
        } 
    } 
}  
int main(){ 
    cin.tie(nullptr)->sync_with_stdio(0);
	cout.tie(nullptr)->sync_with_stdio(0);
    for (long long cs=1;cs<=T;cs++){ 
        solve(cs); 
    } 
    return 0; 
}

解析:
在solve函数中,对于输入的字符串s,从后往前计算每个字符出现的次数的前缀和,这部分代码如下:

for(long long i = n; i; i--) { 
    for(char c = 'a'; c <= 'z'; c++) { 
        sum[c - 'a'][i]=sum[c - 'a'][i + 1]+(s[i]==c); 
    } 
} 

sum是用来统计每个字符在不同位置之后出现的次数的前缀和
接着计算res,res数组预处理表示以某个字符开头以另一个字符结尾的子串个数:

for(long long i = 1; i <= n; i++) { 
    for(char c = 'a'; c <= 'z'; c++) { 
        res[s[i]-'a'][c - 'a']+=sum[c - 'a'][i]; 
    } 
} 

对每个字符构建线段树:

for(char c = 'a'; c <= 'z'; c++) { 
    g[c - 'a'].build(1, 1, n, c); 
} 

当op为2时,直接根据预处理得到的res数组输出以x开头y结尾的子串个数:

else { 
    char x,y; 
    cin>>x>>y; 
    cout<<res[x - 'a'][y - 'a']<<'\n'; 
} 

当op为1时,首先对原来的字符和所有可能的字符组合在res数组中的值进行调整,考虑修改前的字符对统计结果的影响并进行扣除
这里要注意如果i=j会多减一次所以还要再加回来:

for(char x = 'a'; x <= 'z'; x++) { 
    res[s[p]-'a'][x - 'a']-=g[x - 'a'].qry(1, 1, n, p, n); 
    res[x - 'a'][s[p]-'a']-=g[x - 'a'].qry(1, 1, n, 1, p); 
    if(x == s[p])res[x - 'a'][s[p]-'a']++; 
} 

然后修改线段树中原来字符的数量,将原来字符在指定位置的数量减1:

g[s[p]-'a'].modify(1, 1, n, p, -1); 

接着修改字符串中的字符,再修改线段树中修改后字符的数量,将修改后字符在指定位置的数量加1:

s[p]=c; 

g[s[p]-'a'].modify(1, 1, n, p, 1); 

最后再次对修改后的字符和所有可能的字符组合在res数组中的值进行调整
考虑修改后的字符对统计结果的影响并进行增加,这里同样要注意如果i=j会多加一次,所以还要再减回来:

for(char x = 'a'; x <= 'z'; x++) { 
    res[s[p]-'a'][x - 'a']+=g[x - 'a'].qry(1, 1, n, p, n); 
    res[x - 'a'][s[p]-'a']+=g[x - 'a'].qry(1, 1, n, 1, p); 
    if(x == s[p])res[x - 'a'][s[p]-'a']--; 
}