ST表改为线段树,敬请各位豪杰卡常

#include<iostream>
using namespace std;
int n,q,sl[2000000],sr[2000000],op,x,pre[26][500000],l,r,h,num;
unsigned long long w[500000],s[500000],v[2000000],sum;
long long y,a[500000],ans,ss;
int q1[500000],q2[500000],q3[500000],tt,d0,l0,r0;
char c[500000],ch;
inline long long readin(){
	ch=getchar(),h=1,num=0;
	while(ch<'0'||ch>'9'){
		if(ch=='-')h=-1;
		ch=getchar();
	}while(ch>='0'&&ch<='9'){
		num*=10,num+=ch-'0',ch=getchar();
	}return h*num;
}void writeout(long long x){
	if(x<0)putchar('-'),x*=-1;
	if(x>9)writeout(x/10);
	putchar(x%10+'0');
	return;
}void crt(int d,int l,int r){
	if(l!=r){
		crt(d<<1,l,(l+r)>>1);
		crt(d<<1|1,((l+r)>>1)+1,r);
		v[d]=v[d<<1]|v[d<<1|1];
	}else v[d]=w[l];
	sl[d]=l,sr[d]=r;
	return;
}inline unsigned long long qry(int d,int l,int r){
	sum=0,tt=0,q1[tt]=d,q2[tt]=l,q3[tt]=r,tt++;
	while(tt){
		tt--,d0=q1[tt],l0=q2[tt],r0=q3[tt];
		if(l0!=sl[d0]||r0!=sr[d0]){
			if(r0<=sr[d0<<1])q1[tt]=d0<<1,q2[tt]=l0,q3[tt]=r0,tt++;
			else if(l0>=sl[d0<<1|1])q1[tt]=d0<<1|1,q2[tt]=l0,q3[tt]=r0,tt++;
			else{
				q1[tt]=d0<<1,q2[tt]=l0,q3[tt]=sr[d0<<1],tt++;
				q1[tt]=d0<<1|1,q2[tt]=sl[d0<<1|1],q3[tt]=r0,tt++;
			}
		}else sum|=v[d0];
	}return sum;
}inline unsigned long long ran(int l,int r){
	if(l>0)return s[r]^s[l-1];
	return s[r];
}int main(){
	n=readin(),scanf("%s",c);
	for(int i=0;i<n;i++){
		if(i)for(int j=0;j<26;j++)pre[j][i]=pre[j][i-1];
		else for(int j=0;j<26;j++)pre[j][i]=-1;
		pre[c[i]-'a'][i]=i,w[i]=(1<<(c[i]-'a')),s[i]=w[i];
		if(i)s[i]^=s[i-1];
	}crt(1,0,n-1);
	for(int i=0;i<n;i++)a[i]=readin();
	q=readin();
	for(int i=0;i<q;i++){
		op=readin();
		if(op<=1)x=readin(),y=readin(),a[x-1]=y;
		else{
			l=readin(),r=readin(),l--,r--,ans=0,ss=qry(1,l,r);
			for(int j=0;j<26;j++){
				if(!((ss>>j)&1))continue;
				if(ran(l,pre[j][r]-1)&qry(1,pre[j][r],r))continue;
				ans+=a[pre[j][r]];
			}writeout(ans),putchar('\n');
		}
	}return 0;
}