题目链接
发现这不弱于带修莫队，甚至可能还做不了，故不能用“正常”的方法做。
考虑把这至多 \(n + q\) 种数进行 \(m\) 次分组，每次随机把所有数划分到两组，视为 \(0/1\)，然后树状数组维护区间和，判断其是否为 \(k\) 的倍数。
这样若答案为 \(\texttt{NO}\)，则每次查出来的概率至少为 \(\frac 1 2\)。取 \(m = 35\)，错误概率约为 \(2.91 \times 10 ^ {-11}\)，可以接受。
时间复杂度 \(\text O ((n + q) m \log n)\)。
#include<cstdio>
#include<algorithm>
#include<random>
#define N 600005
#define M 40
using namespace std;const int m=35;
int n,q,a[N],op[N],x[N],y[N],z[N];
int tot,lsh[N];
bool occ[M][N];
mt19937 rnd(random_device{}());
int find(int x) {return lower_bound(lsh+1,lsh+tot+1,x)-lsh;}
struct BIT {int tr[N];void add(int p,int c) {for(;p<=n;p+=p&-p) tr[p]+=c;}int ask(int p) {int res=0;for(;p;p&=p-1) res+=tr[p];return res;}int ask(int l,int r) {return ask(r)-ask(l-1);}
} t[M];
int main() {scanf("%d%d",&n,&q);for(int i=1;i<=n;i++) scanf("%d",&a[i]),lsh[++tot]=a[i];for(int i=1;i<=q;i++) {scanf("%d%d%d",&op[i],&x[i],&y[i]);if(op[i]==1) lsh[++tot]=y[i]; else scanf("%d",&z[i]);}sort(lsh+1,lsh+tot+1);tot=unique(lsh+1,lsh+tot+1)-lsh-1;for(int i=1;i<=m;i++) for(int j=1;j<=tot;j++) occ[i][j]=rnd()&1;for(int i=1;i<=n;i++) {a[i]=find(a[i]);for(int j=1;j<=m;j++) if(occ[j][a[i]]) t[j].add(i,1);}for(int i=1;i<=q;i++) {if(op[i]==1) {y[i]=find(y[i]);for(int j=1;j<=m;j++) {int diff=occ[j][y[i]]-occ[j][a[x[i]]];if(diff) t[j].add(x[i],diff);}a[x[i]]=y[i];} else {bool flag=1;for(int j=1;j<=m;j++)if(t[j].ask(x[i],y[i])%z[i]) {flag=0; break;}puts(flag?"YES":"NO");}}return 0;
}