随机取三个 \(2\) 阶方阵 \(A _ 0, A _ 1, A _ 2\) 满足 \(A ^ 2 = I\)，其中 \(A _ i\) 的构造方法为 \(\begin{pmatrix} x & y \\ \frac {1 - x ^ 2} y & -x \end{pmatrix}\)。
然后根据矩阵的结合律（但同时不具备交换律），一段区间合法，有极大的概率当且仅当 \(\displaystyle \prod _ {i = l} ^ r A _ {s _ i} = I\)。
线段树上每个节点维护 \(+0, +1, +2\) 三种情况的区间矩阵乘积，打懒标记维护即可。
时间复杂度 \(\text O ((n + q) \log n \, 2 ^ 3)\).
#include<cstdio>
#include<cstring>
#include<random>
#define N 500005
#define ran(l,r) uniform_int_distribution<>(l,r)(rnd)
using namespace std;const int mod=998244353;
int n,m;
char s[N];
mt19937 rnd(random_device{}());
int qpow(long long x,int y) {int res=1;for(;y;y>>=1) {if(y&1) res=res*x%mod;x=x*x%mod;}return res;
}
int inv(int x) {return qpow(x,mod-2);
}
struct mat {int a[2][2];mat() {memset(a,0,sizeof(a));}int* operator[](int x) {return a[x];}void gen() {int x=ran(0,mod-1),y=ran(0,mod-1);a[0][0]=x,a[0][1]=y,a[1][0]=(1-1ll*x*x%mod+mod)*inv(y)%mod,a[1][1]=(-x+mod)%mod;}friend mat operator*(mat a,mat b) {mat c;c[0][0]=(1ll*a[0][0]*b[0][0]+1ll*a[0][1]*b[1][0])%mod;c[0][1]=(1ll*a[0][0]*b[0][1]+1ll*a[0][1]*b[1][1])%mod;c[1][0]=(1ll*a[1][0]*b[0][0]+1ll*a[1][1]*b[1][0])%mod;c[1][1]=(1ll*a[1][0]*b[0][1]+1ll*a[1][1]*b[1][1])%mod;return c;}
} M[3];
bool check(mat a) {for(int i=0;i<2;i++) for(int j=0;j<2;j++) if(a[i][j]!=(i==j)) return 0;return 1;
}
struct segment_tree {struct st {int l,r,tag; mat c[3];#define l(p) tr[p].l#define r(p) tr[p].r#define c(p) tr[p].c#define tag(p) tr[p].tag} tr[N*4];void update(int p) {for(int i=0;i<3;i++) c(p)[i]=c(p*2)[i]*c(p*2+1)[i];}void inc(int p,int c) {mat d[3]; tag(p)=(tag(p)+c)%3;for(int i=0;i<3;i++) d[i]=c(p)[i];for(int i=0;i<3;i++) c(p)[i]=d[(i+c)%3];}void spread(int p) {if(tag(p)) inc(p*2,tag(p)),inc(p*2+1,tag(p)),tag(p)=0;}void build(int p,int l,int r) {l(p)=l,r(p)=r;if(l==r) {for(int i=0;i<3;i++) c(p)[i]=M[(s[l]-'0'+i)%3];return;}int mid=l+r>>1;build(p*2,l,mid),build(p*2+1,mid+1,r);update(p);}void modify(int p,int l,int r,int c) {if(l<=l(p)&&r>=r(p)) return inc(p,c);spread(p);if(l<=r(p*2)) modify(p*2,l,r,c);if(r>=l(p*2+1)) modify(p*2+1,l,r,c);update(p);}mat ask(int p,int l,int r) {if(l<=l(p)&&r>=r(p)) return c(p)[0];spread(p);if(r<=r(p*2)) return ask(p*2,l,r);if(l>=l(p*2+1)) return ask(p*2+1,l,r);return ask(p*2,l,r)*ask(p*2+1,l,r);}
} t1;
int main() {for(int i=0;i<3;i++) M[i].gen();scanf("%d%d%s",&n,&m,s+1);t1.build(1,1,n);for(int i=1,op,x,y;i<=m;i++) {scanf("%d%d%d",&op,&x,&y);if(op==1) {t1.modify(1,x,y,1);} else {puts(check(t1.ask(1,x,y))?"Yes":"No");}}return 0;
}