思路：用线段树维护正序、倒序的哈希值。

ac15 wa10

#include <bits/stdc++.h>
#define MAXN 1000006
#define ull unsigned long long
#define int ull
using namespace std;
const int mod[4] = {20090723,998244353,1000000007,1000000009};
const int base = 131;
char c[MAXN];
int pb[4][MAXN];
int n,q;
#define ls (p<<1)
#define rs (p<<1|1)
struct node{
	int l,r;
	int Lsum[4],Rsum[4];
}tr[4*MAXN];
void pushUp(int p){
	int Lsiz = tr[ls].r-tr[ls].l+1;
	int Rsiz = tr[rs].r-tr[rs].l+1;
	for(int i=0;i<4;i++){
		tr[p].Lsum[i]=(1ll*tr[ls].Lsum[i]*pb[i][Rsiz]%mod[i]+tr[rs].Lsum[i])%mod[i];
		tr[p].Rsum[i]=(1ll*tr[rs].Rsum[i]*pb[i][Lsiz]%mod[i]+tr[ls].Rsum[i])%mod[i];
	}
}
void build(int l,int r,int p){
	tr[p].l=l,tr[p].r=r;
	if(l==r){
		tr[p].Lsum[0]=tr[p].Rsum[0]=
		tr[p].Lsum[1]=tr[p].Rsum[1]=
		tr[p].Lsum[2]=tr[p].Rsum[2]=
		tr[p].Lsum[3]=tr[p].Rsum[3]=c[l]-'a';return;
	}
	int mid = (l+r)/2;
	build(l,mid,ls);build(mid+1,r,rs);pushUp(p);
}
void modify(int x,int c,int p){
	if(tr[p].l==tr[p].r){
		tr[p].Lsum[0]=tr[p].Rsum[0]=
		tr[p].Lsum[1]=tr[p].Rsum[1]=
		tr[p].Lsum[2]=tr[p].Rsum[2]=
		tr[p].Lsum[3]=tr[p].Rsum[3]=c;return;
	}
	if(x<=tr[ls].r)modify(x,c,ls);
	else modify(x,c,rs);
	pushUp(p);
}
int queryL(int l,int r,int mdt,int p=1){
	if(l<=tr[p].l&&r>=tr[p].r)return tr[p].Lsum[mdt];
	if(l<=tr[ls].r&&r>=tr[rs].l){
		int Rsiz = r-tr[rs].l+1;
		return (queryL(l,r,mdt,ls)*pb[mdt][Rsiz]%mod[mdt]+queryL(l,r,mdt,rs))%mod[mdt];
	}
	if(l<=tr[ls].r){
		return queryL(l,r,mdt,ls);
	}else return queryL(l,r,mdt,rs);
}
int queryR(int l,int r,int mdt,int p=1){
	if(l<=tr[p].l&&r>=tr[p].r)return tr[p].Rsum[mdt];
	if(l<=tr[ls].r&&r>=tr[rs].l){
		int Lsiz = tr[ls].r-l+1;
		return (queryR(l,r,mdt,rs)*pb[mdt][Lsiz]%mod[mdt]+queryR(l,r,mdt,ls))%mod[mdt];
	}
	if(l<=tr[ls].r){
		return queryR(l,r,mdt,ls);
	}else return queryR(l,r,mdt,rs);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr),cout.tie(nullptr);
	cin>>n>>q;
	cin>>(c+1);
	pb[0][0]=pb[1][0]=1;
	pb[2][0]=pb[3][0]=1;
	for(int j=0;j<4;j++)
	for(int i=1;i<MAXN;i++)pb[j][i]=pb[j][i-1]*base%mod[j];
	build(1,n,1);
	while(q--){
		int op;cin>>op;
		if(op==1){
			int x;char C;cin>>x>>C;C-='a';
			//cerr<<6;
			modify(x,C,1);
		}else{
			int l,r;cin>>l>>r;//cerr<<7;
			//cerr<<queryL(l,r)<<" "<<queryR(l,r)<<"\n";
			bool f = 1;
			for(int i=0;i<4;i++)f&=(queryL(l,r,i)==queryR(l,r,i));
			cout<<(f ? "Yes\n" : "No\n");
		}
	}
	return 0;
}