题解 Codeforces 1746F Kazaee

题意

给定长度为 \(n\) 的数组 \(a\)，和 \(q\) 次操作，支持：

• 给定 \(i,x\)，修改 \(a_i\) 为 \(x\)
• 给定 \(l,r,k\)，查询 \([l,r]\) 中是否每个数的出现次数都是 \(k\) 的倍数

\(1 \leq n,q \leq 3 \times 10^5,1 \leq a_i,x \leq 10^9,1 \leq k \leq n\)

题解

构造随机映射 \(f(x) \to b_x\)，那么区间的 \(b_x\) 和是 \(k\) 的倍数是答案为 YES 的必要条件。我们注意到区间和模 \(k\) 随机，这意味着我们有 \(\dfrac{1}{k} (k \geq 2)\) 的概率误判，那么我们构造 \(25\) 个不同的随机映射，答案为 YES 当且仅当每个随机映射中 \(b_x\) 和都是 \(k\) 的倍数，此时错误率为 \(\dfrac{m}{k^{25}}\)，取 \(k=2\) 时单组数据错误率约为 \(0.008\)，可以接受。

修改操作用树状数组维护即可。

# include <bits/stdc++.h>

const int N=300010,INF=0x3f3f3f3f,B=25;

int n,m;
int a[N];

typedef long long ll;

std::map <int,int> mp;
int cnt;

inline int mpc(int x){
	if(!x) return 0;
	if(!mp[x]) mp[x]=++cnt;
	return mp[x];
}

std::mt19937 rng(time(0));

struct bit{
	int b[N*2];
	ll s[N];
	inline void init(void){
		for(int i=1;i<=n+m;++i) b[i]=rng();
		return;
	}
	inline int lowbit(int x){
		return x&(-x);
	}
	inline void add(int x,int v){
		for(;x<=n;x+=lowbit(x)) s[x]+=v;
		return;
	}
	inline int query(int l,int r,int k){
		ll ans=0;
		--l;
		for(;l;l-=lowbit(l)) ans-=s[l];
		for(;r;r-=lowbit(r)) ans+=s[r];
		return ans%k;
	}
	inline void modify(int x,int pre,int nex){
		add(x,-b[pre]),add(x,b[nex]);
		return;
	}
}ch[41];

inline int read(void){
	int res,f=1;
	char c;
	while((c=getchar())<'0'||c>'9')
		if(c=='-')f=-1;
	res=c-48;
	while((c=getchar())>='0'&&c<='9')
		res=res*10+c-48;
	return res*f;
}
inline void modify(int x,int v){
	int pre=mpc(a[x]),nex=mpc(v);
	a[x]=v;
	for(int i=1;i<=B;++i) ch[i].modify(x,pre,nex);
	return;
}
inline int query(int l,int r,int k){
	for(int i=1;i<=B;++i) if(ch[i].query(l,r,k)) return 0;
	return 1;
}

int main(void){
	n=read(),m=read();
	for(int i=1;i<=B;++i) ch[i].init();
	for(int i=1;i<=n;++i) modify(i,read());
	while(m--){
		int op=read(),l=read(),r=read();
		if(op==2) puts(query(l,r,read())?"YES":"NO");
		else modify(l,r);
	}
	

	return 0;
}