成功拿下本题第一个AC

思路

首先考虑暴力，每一次询问都枚举每一个字符，再暴力枚举整个区间，判断是否出现，最后总计数即可，复杂度$O(QN)$。

由于我们使用的是区间的求和，考虑用前缀和优化，定义$s_{i,c}$表示前$i$个字符中字符$c$出现的次数，但这样子修改操作依旧是$O(N)$的复杂度。

这时考虑树状数组优化，不会树状数组的出门左转

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
char str[N];
int s[N][26],n,q;//前i位j出现次数
void add(int c,int x,int k){for(;x<=n;x+=x&-x)s[x][c]+=k;} 
int sum(int c,int x)
{
	int res=0;
	for(;x;x-=x&-x)res+=s[x][c];
	return res;
}
int main()
{
	scanf("%d%s%d",&n,str+1,&q);
	for(int i=1;i<=n;i++)add(str[i]-'a',i,1);
	while(q--)
	{
		int op,l,r;char ss[3];scanf("%d%d",&op,&l);
		if(op==1)
		{
			scanf("%s",ss+1);
			add(str[l]-'a',l,-1);
			add(ss[1]-'a',l,1);
			str[l]=ss[1];
		}
		else
		{
			scanf("%d",&r);
			int cnt=0;
			for(int i=0;i<26;i++)if(sum(i,r)!=sum(i,l-1))cnt++;
			printf("%d\n",cnt);
		}
	}
	return 0;
}