1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| #include<bits/stdc++.h>
using namespace std;
const int base1=131;
const int base2=13331;
const int mod1=998244353;
const int mod2=1e9+7;
const int maxn=2e5+2;
int pos[maxn],p;
int hsh1[maxn][2],hsh2[maxn][2];
int pow1[maxn],pow2[maxn];
void init_hsh(){
pow1[0]=pow2[0]=1;
for(int i=1;i<=p;i++){
hsh1[i][0]=(1ll*hsh1[i-1][0]*base1+pos[i]%2+1)%mod1;
hsh1[i][1]=(1ll*hsh1[i-1][1]*base1+!(pos[i]%2)+1)%mod1;
pow1[i]=1ll*base1*pow1[i-1]%mod1;
hsh2[i][0]=(1ll*hsh2[i-1][0]*base2+pos[i]%2+1)%mod2;
hsh2[i][1]=(1ll*hsh2[i-1][1]*base2+!(pos[i]%2)+1)%mod2;
pow2[i]=1ll*base2*pow2[i-1]%mod2;
}
}
typedef pair<int,int> pr;
pr gethsh(int l,int r,int st){
if(st%2){
return pr((hsh1[r][0]-1ll*pow1[r-l+1]*hsh1[l-1][0]%mod1+mod1)%mod1,(hsh2[r][0]-1ll*hsh2[l-1][0]*pow2[r-l+1]%mod2+mod2)%mod2);
}else{
return pr((hsh1[r][1]-1ll*pow1[r-l+1]*hsh1[l-1][1]%mod1+mod1)%mod1,(hsh2[r][1]-1ll*hsh2[l-1][1]*pow2[r-l+1]%mod2+mod2)%mod2);
}
}
int n;
char s[maxn];
int main(){
cin>>n;
cin>>(s+1);
for(int i=1;i<=n;i++)
if(s[i]=='0')
pos[++p]=i;
init_hsh();
int q;
cin>>q;
int x,y,l;
while(q--){
cin>>x>>y>>l;
int xl=lower_bound(pos,pos+p+1,x)-pos;
int xr=upper_bound(pos,pos+p+1,x+l-1)-pos-1;
int yl=lower_bound(pos,pos+p+1,y)-pos;
int yr=upper_bound(pos,pos+p+1,y+l-1)-pos-1;
pr px=gethsh(xl,xr,x);
pr py=gethsh(yl,yr,y);
cout<<(px==py?"Yes":"No")<<endl;
}
return 0;
}
/*
10
0100001001
1
2 9 2
*/
|
