题目链接。
这个数据范围，显然出题人出这题的本意不是让我们用带修莫队过题（当然有人过），而我们又难以找到很好的 \(\text{DS}\) 维护方法。
故考虑另辟蹊径。对于所有 \(a_i,x\)，不妨把值相同的归入一个等价类。对于一个等价类，随机出一个 \([0,1]\) 间的权值。我们把等价类的权值代替原来的 \(a_i,x\)，会发现：此时我们输出 YES 的必要条件还是：区间 \([l,r]\) 内是否每个出现过的正整数的出现次数都是 \(k\) 的倍数。
尝试分析这样做的正确概率。因为我们当前的判断判断条件是必要条件而不是充分条件，所以只可能把 NO 误判成 YES。假设区间中有 \(x\) 个数出现次数不为 \(k\) 的倍数——记这些数为 \(i_1,i_2,\dots,i_r\)，他们分别在区间中出现了 \(c_{i_1},c_{i_2},\dots,c_{i_r}\) 次。对于一个等价类随机一个 \([0,1]\) 就等价于对于每个数决策它选不选。最终我们会误判当且仅当选出的数总和是 \(k\) 的倍数。由于数据随机，因此单组询问错误的概率约为 \(\frac{1}{k}\)（\(k\) 取 \(2\) 时合法且达到最大），\(q\) 组询问的错误概率不超过为 \(\frac{q}{2}\)。
但如果对这个随机再判断的过程做 \(T\) 次呢（最终输出 YES 当且仅当每次都满足条件）？只有每次都误判，最终才会误判答案。也就是说，这个做法正确率至少达到了 \(q\times2^{-T}\)。
\(T\) 建议取到 \(30\) 左右，再大容易被卡常。
点击查看代码
#include <bits/stdc++.h>
#define FL(i, a, b) for(int i = (a); i <= (b); i++)
#define FR(i, a, b) for(int i = (a); i >= (b); i--)
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int N = 3e5 + 10;
struct Q{int op, x, y, k;} p[N];
int n, q, a[N], key[N * 2], ans[N];
unordered_map<int, int> mp;
inline int read(){
int x = 0, f = 1;
char ch = getchar();
while(!isdigit(ch)){if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
return x * f;
}
struct BIT{
int n = 0, c[N];
void clear(){fill(c, c + n + 1, 0);}
void resize(int t){fill(c + n + 1, c + t + 1, 0); n = t;}
void add(int x, int v){
for(; x <= n; x += x & -x) c[x] += v;
}
int ask(int x, int ret = 0){
for(; x; x -= x & -x) ret += c[x];
return ret;
}
} b;
int main(){
b.resize(n = read()), q = read();
int op, x, y, k, flag;
FL(i, 1, n){
a[i] = read();
if(!mp[a[i]]) mp[a[i]] = rnd() % (1ll << 31);
key[i] = mp[a[i]];
}
FL(i, 1, q){
p[i].op = read(), p[i].x = read(), p[i].y = read();
if(p[i].op == 1){
if(!mp[p[i].y]) mp[p[i].y] = rnd() % (1ll << 31);
key[n + i] = mp[p[i].y];
}
if(p[i].op == 2) p[i].k = read(); ans[i] = 1;
}
FL(j, 1, 30){
unordered_map<int, int>().swap(mp), b.clear();
FL(i, 1, n) b.add(i, a[i] = key[i] & 1), key[i] >>= 1;
FL(i, 1, q) if(ans[i]){
op = p[i].op, x = p[i].x;
if(op == 1){
y = key[n + i] & 1, key[n + i] >>= 1;
b.add(x, y - a[x]), a[x] = y;
}
else{
y = p[i].y, k = p[i].k, flag = 1;
if((b.ask(y) - b.ask(x - 1)) % k) ans[i] = 0;
}
}
}
FL(i, 1, q) if(p[i].op > 1) printf(ans[i]? "YES\n" : "NO\n");
return 0;
}