此题的一种哈希做法是使用字符串哈希令 $hash(x)=a^x \mod p$，其中 $a$ 随机选取。那么此题 $V=10^9$，当做一个长度为 $10^9$ 的字符串，类比 字符串哈希的结论 可以得到 任意两个不同集合冲突概率 $\le \frac{V-1}{p}$，取两个质数 $p_1=10^9+7,p_2=10^8+7$ 显然可以通过。

但是这个概率估太大了，经过测试发现$p_1=1013,p_2=1019$ 都可以过。所以这种哈希方式是否存在一些较为准确的冲突概率估计方法，或者是数据某种意义上水了？

$p_1=1013,p_2=1019$ code：(分时段测试了五次全部 $\text{AC}$，应该不是运气导致的)

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define db double
#define i128 __int128
#define ull unsigned long long

const ll mod_1=1013;
const ll mod_2=1019;
const ll B=1e9;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());//unsigned int!
ll b_1=rng()%(mod_1-3)+2;
ll b_2=rng()%(mod_2-3)+2;
//ll b_1=rng();
//ll b_2=rng();

const ll N=3e5;
int n,q;
ll a[N+10];
ll fpow(ll a,ll p,const ll mod){
	ll res=1;
	while(p){
//		cout<<p<<'\n';
		if(p&1) res=res*a%mod;
		a=a*a%mod,p>>=1;
	}
	return res;
}

struct BIT{
	ll val[N+10];
	int lowbit(int x){return x&(-x);}
	void add(int p,ll x,const ll mod){for(int i=p;i<=N;i+=lowbit(i)) val[i]=(val[i]+x)%mod;}
	ll query(int p,const ll mod){
		ll res=0;
		for(int i=p;i;i-=lowbit(i)) res=(res+val[i])%mod;
		return res;
	}
}tr_0,tr_1,tr_2;

int main(){
//	b_1=10;
//	cout<<b_1<<' '<<b_2<<'\n';
//	freopen("P5278_1.in","r",stdin);
//	freopen("P5278.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++) cin>>a[i],tr_0.add(i,a[i],LONG_LONG_MAX),tr_1.add(i,fpow(b_1,a[i],mod_1),mod_1),tr_2.add(i,fpow(b_2,a[i],mod_2),mod_2);
	int cnt=0;
	for(int i=1;i<=q;i++){
		int op;
		cin>>op;
//		cout<<i<<'\n';
		if(op==2){
			int l,r;
			ll k;
			cin>>l>>r>>k;
			l^=cnt,r^=cnt,k^=cnt;
			
//			cout<<l<<' '<<r<<' '<<k<<'\n';
			
			ll s=tr_0.query(r,LONG_LONG_MAX)-tr_0.query(l-1,LONG_LONG_MAX);
			ll L=1.0*s/(r-l+1)-1.0*(r-l)*k/2;
			if(L<0){
				cout<<"No\n";
				continue;
			}
			ll len=r-l+1;
			
//			cout<<s<<' '<<L<<'\n';
			ll val=fpow(b_1,k,mod_1);
			
//			cout<<"DEBUG:"<<L<<' '<<len<<" "<<val<<' '<<fpow(b_1,L,mod_1)*(fpow(val,len,mod_1)+mod_1-1)%mod_1<<'\n';
//			cout<<(tr_1.query(r,mod_1)-tr_1.query(l-1,mod_1)+mod_1)%mod_1*(val-1+mod_1)%mod_1<<'\n';
			if(val!=1){
				if(fpow(b_1,L,mod_1)*(fpow(val,len,mod_1)+mod_1-1)%mod_1!=
				(tr_1.query(r,mod_1)-tr_1.query(l-1,mod_1)+mod_1)%mod_1*(val-1+mod_1)%mod_1){
					cout<<"No\n";
					continue;
				}
			}
			else{
				if(fpow(b_1,L,mod_1)*len%mod_1!=
				(tr_1.query(r,mod_1)-tr_1.query(l-1,mod_1)+mod_1)%mod_1){
					cout<<"No\n";
					continue;
				}
			}
			
			val=fpow(b_2,k,mod_2);
			
//			cout<<"DEBUG:"<<L<<' '<<len<<" "<<val<<' '<<fpow(b_2,L,mod_2)*(fpow(val,len,mod_2)+mod_2-1)%mod_2<<'\n';
//			cout<<(tr_2.query(r,mod_2)-tr_2.query(l-1,mod_2)+mod_2)%mod_2*(val-1+mod_2)%mod_2<<'\n';
			if(val!=1){
				if(fpow(b_2,L,mod_2)*(fpow(val,len,mod_2)+mod_2-1)%mod_2!=
				(tr_2.query(r,mod_2)-tr_2.query(l-1,mod_2)+mod_2)%mod_2*(val-1+mod_2)%mod_2){
					cout<<"No\n";
					continue;
				}
			}
			else{
				if(fpow(b_2,L,mod_2)*len%mod_2!=
				(tr_2.query(r,mod_2)-tr_2.query(l-1,mod_2)+mod_2)%mod_2){
					cout<<"No\n";
					continue;
				}
			}
			
			cout<<"Yes\n";	
			cnt++;	
		}
		else{
			int p,x;
			cin>>p>>x;
			p^=cnt,x^=cnt;
			tr_0.add(p,-a[p],LONG_LONG_MAX);
			tr_1.add(p,mod_1-fpow(b_1,a[p],mod_1),mod_1),tr_2.add(p,mod_2-fpow(b_2,a[p],mod_2),mod_2);
			a[p]=x;
			tr_0.add(p,a[p],LONG_LONG_MAX);
			tr_1.add(p,fpow(b_1,a[p],mod_1),mod_1),tr_2.add(p,fpow(b_2,a[p],mod_2),mod_2);
		}
	}
	return 0;
}
/*fc P5278.out P5278_1.out*/