#include<bits/stdc++.h>
#define int long long
const int N=300001,mod=1e11+3;
using namespace std;
struct node{
	int sum,mx,mn;
}s[N<<2];
int a[N],cnt=0;
#define mid ((l+r)>>1)
void update(node&x,node y){
	x.sum=(x.sum+y.sum)%mod,x.mx=max(x.mx,y.mx),x.mn=min(x.mn,y.mn);
}
void build(int k,int l,int r){
	if(l==r)return s[k]=(node){a[l]*a[l]%mod,a[l],a[l]},void();
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	s[k]=(node){(s[k<<1].sum+s[k<<1|1].sum)%mod,max(s[k<<1].mx,s[k<<1|1].mx),min(s[k<<1].mn,s[k<<1|1].mn)};
}
void change(int k,int l,int r,int x,int v){
	if(l==x&&r==x)return s[k]=(node){v*v%mod,v,v},void();
	if(x<=mid)change(k<<1,l,mid,x,v);
	else change(k<<1|1,mid+1,r,x,v);
//	s[k]=(node){(s[k<<1].sum+s[k<<1|1].sum)%mod,max(s[k<<1].mx,s[k<<1|1].mx),min(s[k<<1].mn,s[k<<1|1].mn)};
}
node ask(int k,int l,int r,int x,int y){
	if(x<=l&&r<=y)return s[k];
	node res=(node){0,INT_MIN,INT_MAX};
	if(x<=mid)update(res,ask(k<<1,l,mid,x,y));
	if(y>mid)update(res,ask(k<<1|1,mid+1,r,x,y));
	return res;
}
#undef mid
string chk(int l,int r,int k,node x){
	if(l==r||(k==0&&x.mx==x.mn))return cnt++,"Yes\n";
	if(x.mx-x.mn!=(r-l)*k)return "No\n";
	int len=(r-l)/k;
	if((6*x.mn%mod*x.mn%mod*(len+1)%mod+(len*(len+1)%mod*(2*len+1)%mod*k%mod+x.mn*len%mod*(len+1)%mod*6%mod)*k%mod)%mod!=x.sum*6%mod)return "No\n";
	return cnt++,"Yes\n";
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int n,m,i,l,r,k,x,y,op;
	cin>>n>>m;
	for(i=1;i<=n;i++)cin>>a[i];
	build(1,1,n);
	while(m--){
		cin>>op;
		switch(op){
			case 1:cin>>x>>y,x^=cnt,y^=cnt,change(1,1,n,x,y);break;
			case 2:cin>>l>>r>>k,l^=cnt,r^=cnt,k^=cnt,cout<<chk(l,r,k,ask(1,1,n,l,r));break;
		}
	}
	return 0;
}

这会 TLE。

#include<bits/stdc++.h>
#define int long long
const int N=300001,mod=1e11+3;
using namespace std;
struct node{
	int sum,mx,mn;
}s[N<<2];
int a[N],cnt=0;
#define mid ((l+r)>>1)
void update(node&x,node y){
	x.sum=(x.sum+y.sum)%mod,x.mx=max(x.mx,y.mx),x.mn=min(x.mn,y.mn);
}
void build(int k,int l,int r){
	if(l==r)return s[k]=(node){a[l]*a[l]%mod,a[l],a[l]},void();
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	s[k]=(node){(s[k<<1].sum+s[k<<1|1].sum)%mod,max(s[k<<1].mx,s[k<<1|1].mx),min(s[k<<1].mn,s[k<<1|1].mn)};
}
void change(int k,int l,int r,int x,int v){
	if(l==x&&r==x)return s[k]=(node){v*v%mod,v,v},void();
	if(x<=mid)change(k<<1,l,mid,x,v);
	else change(k<<1|1,mid+1,r,x,v);
	return;
	s[k]=(node){(s[k<<1].sum+s[k<<1|1].sum)%mod,max(s[k<<1].mx,s[k<<1|1].mx),min(s[k<<1].mn,s[k<<1|1].mn)};
}
node ask(int k,int l,int r,int x,int y){
	if(x<=l&&r<=y)return s[k];
	node res=(node){0,INT_MIN,INT_MAX};
	if(x<=mid)update(res,ask(k<<1,l,mid,x,y));
	if(y>mid)update(res,ask(k<<1|1,mid+1,r,x,y));
	return res;
}
#undef mid
string chk(int l,int r,int k,node x){
	if(l==r||(k==0&&x.mx==x.mn))return cnt++,"Yes\n";
	if(x.mx-x.mn!=(r-l)*k)return "No\n";
	int len=(r-l)/k;
	if((6*x.mn%mod*x.mn%mod*(len+1)%mod+(len*(len+1)%mod*(2*len+1)%mod*k%mod+x.mn*len%mod*(len+1)%mod*6%mod)*k%mod)%mod!=x.sum*6%mod)return "No\n";
	return cnt++,"Yes\n";
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int n,m,i,l,r,k,x,y,op;
	cin>>n>>m;
	for(i=1;i<=n;i++)cin>>a[i];
	build(1,1,n);
	while(m--){
		cin>>op;
		switch(op){
			case 1:cin>>x>>y,x^=cnt,y^=cnt,change(1,1,n,x,y);break;
			case 2:cin>>l>>r>>k,l^=cnt,r^=cnt,k^=cnt,cout<<chk(l,r,k,ask(1,1,n,l,r));break;
		}
	}
	return 0;
}

这会 MLE。