哈希+线段树WA on#6求调
查看原帖
哈希+线段树WA on#6求调
763878
Jerry_heng楼主2024/8/8 14:19
#include<bits/stdc++.h>
#define db double
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
#define pii pair<int,int>
#define int long long
using namespace std;
inline int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f; 
}
const int md=1e9+7,bas=998244353,mxn=2e5+10;
char ch[mxn];
int n,s[mxn],pw[mxn],T,inv;
struct node{
	int l,r,len,sum;
}tree[mxn<<2];
node pushup(node x,node y){
	node res=(node){x.l,y.r,x.len+y.len,(x.sum*pw[y.len]+y.sum)%md};
	if(x.r&&y.l){
		res.len-=2;
		if(x.len==1)res.sum=(y.sum-2*pw[y.len-1]%md+md)%md;
		else if(y.len==1)res.sum=(x.sum-2+md)%md*inv%md;
		else res.sum=((x.sum-2+md)%md*pw[x.len+y.len-2]%md+y.sum-2*pw[y.len-1]%md+md)%md;
		if(x.len==1)res.l=0;
		if(y.len==1)res.r=0;
	}
	return res;
}
void build(int o,int l,int r){
	if(l==r){
		tree[o]=(node){0,0,1,s[l]};
		if(s[l]==2)tree[o].l=tree[o].r=1;
		return;
	}
	int mid=(l+r)>>1;
	build(o*2,l,mid);
	build(o*2+1,mid+1,r);
	tree[o]=pushup(tree[o*2],tree[o*2+1]);
}
node query(int o,int l,int r,int L,int R){
	if(L<=l&&r<=R)return tree[o];
	int mid=(l+r)>>1;
	if(R<=mid)return query(o*2,l,mid,L,R);
	else if(L>mid)return query(o*2+1,mid+1,r,L,R);
	else return pushup(query(o*2,l,mid,L,R),query(o*2+1,mid+1,r,L,R));
}
int quickpw(int x,int y){
    int ans=1;
    while(y){
        if(y&1)ans=ans*x%md;
        x=x*x%md;
        y>>=1;
    }
    return ans;
}
signed main(){
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
    n=read();
    scanf("%s",ch+1);
    T=read();
    inv=quickpw(bas,md-2);
    for(int i=1;i<=n;i++)
    	s[i]=ch[i]-'0'+1;
    pw[0]=1;
    for(int i=1;i<=n;i++)
    	pw[i]=pw[i-1]*bas%md;
    build(1,1,n);
    while(T--){
    	int l=read(),r=read(),len=read();
    	node res1=query(1,1,n,l,l+len-1),res2=query(1,1,n,r,r+len-1);
    	if(res1.sum==res2.sum&&res1.len==res2.len)puts("Yes");
    	else puts("No");
    }
    return 0;
}
2024/8/8 14:19
加载中...