评测记录

#include <bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f,N=1e6+5;
struct Tree{
	int mn,mx,mx_pre,d;
}T[N<<2],T2[N<<2];
int a[N],c[N],n,m,pre[N];
int cnt;
map<int,set<int> > mp;
set<int>::iterator ite;
int gcd(int x,int y){
	if(y==0)return x;
	return gcd(y,x%y);
}
void pushup(int u){
	T[u].mn=min(T[u*2].mn,T[u*2+1].mn);
	T[u].mx=max(T[u*2].mx,T[u*2+1].mx);
	T[u].mx_pre=max(T[u*2].mx_pre,T[u*2+1].mx_pre);
}
void build(int l,int r,int u){
	if(l==r){
		//cout <<l<<" "<<u<<"\n";
		T[u].mn=T[u].mx=a[l];
		T[u].mx_pre=pre[l];
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,u*2);
	build(mid+1,r,u*2+1);
	pushup(u);
}
void build2(int l,int r,int u){
	if(l==r){
		T2[u].d=c[l];
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,u*2);
	build(mid+1,r,u*2+1);
	T2[u].d=gcd(T2[u*2].d,T2[u*2+1].d);
}
int find_mx(int l,int r,int L,int R,int u){
	if(l<=L&&R<=r){
		//cout <<l<<" "<<u<<"\n";
		return T[u].mx;
	}
	int a=-1,b=-1,mid=(L+R)>>1;
	if(l<=mid) a=find_mx(l,r,L,mid,u*2);
	if(r>mid) b=find_mx(l,r,mid+1,R,u*2+1);
	//cout <<L<<" "<<R<<" "<<a<<" "<<b<<"\n";
	return max(a,b);
}
int find_mn(int l,int r,int L,int R,int u){
	if(l<=L&&R<=r) return T[u].mn;
	int a=inf,b=inf,mid=(L+R)>>1;
	if(l<=mid) a=find_mn(l,r,L,mid,u*2);
	if(r>mid) b=find_mn(l,r,mid+1,R,u*2+1);
	//cout <<L<<" "<<R<<" "<<a<<" "<<b<<"\n";
	return min(a,b);
}
int find_pre(int l,int r,int L,int R,int u){
	if(l<=L&&R<=r) return T[u].mx_pre;
	int a=-1,b=-1,mid=(L+R)>>1;
	if(l<=mid) a=find_pre(l,r,L,mid,u*2);
	if(r>mid) b=find_pre(l,r,mid+1,R,u*2+1);
	return max(a,b);
}
int find_d(int l,int r,int L,int R,int u){
	if(l<=L&&R<=r) return T2[u].d;
	int a=0,b=0,mid=(L+R)>>1;
	if(l<=mid) a=find_d(l,r,L,mid,u*2);
	if(r>mid) b=find_d(l,r,mid+1,R,u*2+1);
	return gcd(a,b);
}
void mod1(int l,int r,int pos,int x,int u){
	if(l==r){
		T[u].mn=T[u].mx=x;
		T[u].mx_pre=pre[l];
		//cout <<l<<" "<<r<<" "<<T[u].mx<<endl;
		return;
	}
	int mid=(l+r)>>1;
	if(pos<=mid) mod1(l,mid,pos,x,u*2);
	else mod1(mid+1,r,pos,x,u*2+1);
	pushup(u);
	//cout <<l<<" "<<r<<" "<<T[u].mx<<endl;
}
void mod2(int l,int r,int pos,int u){
	if(l==r){
		T2[u].d=c[pos];
		return;
	}
	int mid=(l+r)>>1;
	if(pos<=mid) mod2(l,mid,pos,u*2);
	else mod2(mid+1,r,pos,u*2+1);
	T2[u].d=gcd(T2[u*2].d,T2[u*2+1].d);
	//cout <<L<<" "<<R<<" "<<d[u]<<endl;
}
bool check(int l,int r,int k){
	if(l==r)return 1;
	int mn=find_mn(l,r,1,n,1);
	int mx=find_mx(l,r,1,n,1);
	int mx_pre=find_pre(l,r,1,n,1);
	int d=find_d(l,r-1,1,n-1,1);
	if(!(mx-mn)&&!k)return 1;
	//cout <<mn<<" "<<mx<<" "<<mx_pre<<" "<<d<<"\n";
	if(mx-mn!=1ll*(r-l)*k)return 0;
	if(k>0&&mx_pre>=l)return 0;
	if(d!=k)return 0;
	return 1;
}
int main(){
	cin >>n>>m;
	for(int i=1;i<=n;i++) cin >>a[i];
	for(int i=1;i<n;i++)c[i]=abs(c[i+1]-c[i]);
	for(int i=1;i<=n;i++){
		if(mp[a[i]].size()==0){
			pre[i]=-1;
		}else{
			ite=mp[a[i]].end();
			--ite;
			pre[i]=*ite;
		}
		mp[a[i]].insert(i);
	}
	build(1,n,1);
	build2(1,n-1,1);
	//cout <<find_mx(4,4,1,n,1)<<"\n";
	for(int i=1;i<=m;i++){
		long long op,x,y,l,r,k;
		cin >>op;
		if(op==1){
			cin >>x>>y;
			x^=cnt;
			y^=cnt;
			ite=mp[a[x]].find(x);
			if(ite!=mp[a[x]].end())++ite;
			pre[*ite]=pre[x];
			mod1(1,n,*ite,a[*ite],1);
			mp[a[x]].erase(x);
			a[x]=y;
			ite=mp[a[x]].lower_bound(x);
			if(ite!=mp[a[x]].end())pre[*ite]=x,mod1(1,n,*ite,a[*ite],1);
			if(ite==mp[a[x]].begin())pre[x]=-1;
			else pre[x]=*--ite;
			mp[a[x]].insert(x);
			c[x]=abs(a[x+1]-a[x]);
			c[x-1]=abs(a[x]-a[x-1]);
			mod1(1,n,x,y,1);
			mod2(1,n-1,x,1);
			if(x-1>0)mod2(1,n-1,x-1,1);
		}else{
			cin >>l>>r>>k;
			l^=cnt;
			r^=cnt;
			k^=cnt;
			if(l>r)swap(l,r);
			if(check(l,r,k)){
				cout <<"Yes\n";
				cnt++;
			}else cout <<"No\n";
		}
	}
	//cout <<find_mx(4,4,1,n,1);
	return 0;
}