C++ 解法, 执行用时: 121ms, 内存消耗: 2420K, 提交时间: 2021-07-21 22:57:11

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int N=1e5+10;
const int maxn=1e5;

ull H[N];
ull t[N];
char s[N];

inline int lowbit(int x){
	return x&-x;
}
ull getsum(int x){
	ull res=0;
	for(int i=x;i>0;i-=lowbit(i)){
		res+=t[i];
	}
	return res;
}
void add(int x,ull y){
	for(int i=x;i<=maxn;i+=lowbit(i)){
		t[i]+=y;
	}
}
bool check(int l1,int r1,int l2,int r2){
	ull res1=getsum(r1)-getsum(l1-1);
	ull res2=getsum(r2)-getsum(l2-1);
	if(l1<=l2){
		return res1*H[l2-l1]==res2;
	}
	else{
		return res2*H[l1-l2]==res1;
	}
}
int main()
{
	int seed=31;
	H[0]=1;
	for(int i=1;i<=100000;i++){
		H[i]=H[i-1]*seed;
	}
	int n,m;
	scanf("%d%d",&n,&m);
	scanf("%s",s+1);
	for(int i=1;i<=n;i++){
		add(i,(s[i]-'a')*H[i]);
	}
	for(int i=1;i<=m;i++){
		int op;
		scanf("%d",&op);
		if(op==1){
			int x;
			char c[3];
			scanf("%d%s",&x,c);
			add(x,-(s[x]-'a')*H[x]);
			s[x]=c[0];
			add(x,(s[x]-'a')*H[x]);
		}
		else{
			int l1,r1,l2,r2;
			scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
			if(r1-l1!=r2-l2){
				printf("NO\n");
				continue;
			}
			int l=1,r=r1-l1+1,mid;
			while(l<=r){
				mid=(l+r)>>1;
				if(check(l1,l1+mid-1,l2,l2+mid-1)){
					l=mid+1;
				}
				else r=mid-1;
			}
			if(l==r1-l1+2){
				printf("YES\n");
				continue;
			}
			int pos=r+1;
			if(check(l1+pos,r1,l2+pos,r2)){
				printf("YES\n");
			}
			else printf("NO\n");
		}
	}
	return 0;
}