QOJ19007 2026 上海市赛 E 完美区间
Note
给你长度为 $n$ 的整数序列 $S$，满足序列内元素两两互质，完成 $T$ 组查询或修改操作：
- 查询：给你一个区间 $[l, r]$，问是否是一个完美区间；指的是，对于每一个数 $x$ 在区间内，我们记录他的出现次数是 $c_x$，都有 $c_x \mod{x} = 0$
- 修改：把一个位置 $p$ 上的 $S_p := x$，保证修改后也是两两互质的
「约束」：$n, T \le 200000, \ \ x,S_i \le 10^8$
好牛逼的 Ad-hoc！
如果你能想到一个数 $x$ 出现了其值的倍数次数一定有 $x^{-1} \times c_x$ 是一个整数的话，你就自然可以想到：
- 实际上就是 $t = x^{-1} \times c_x$ 的话，有 $t - round(t) = 0$，对于每个 $x$ 都满足
然后你要能想到，如果两两互质的话，他乘起来就不会干扰，于是有：
-
$t = pre[r] - pre[l - 1]$ ，如果有 $t- round(t) = 0$ ，那么就是
Yes，反之是No
这题就写完了，
你只需要维护一个 $x^{-1}$ 的任何一个可以修改查询前缀和的东西就行了
//no-unlocked
const ll M1 = 2013265921, M2 = 2281701377;
{
int @n, @T;
fenwick<ll> t1, t2;
t1.malloc(n + 1); t1.init(n + 1); t2.malloc(n + 1); t2.init(n + 1);
ll a[n];
rep(i, n) {
ll @x; a[i] = x;
t1.add(i, powmod(a[i], M1 - 2, M1)); t2.add(i, powmod(a[i], M2 - 2, M2));
}
rep(T) {
int @op;
if(op == 0) {
int @l, @r; l --, r --;
ll r1 = t1.get(r), r2 = t2.get(r);
ll l1 = t1.get(l - 1), l2 = t2.get(l - 1);
wt((r1 - l1 + M1) % M1 == (r2 - l2 + M2) % M2 ? "yes" : "no");
} else {
int @p; ll @x; p --;
t1.add(p, -powmod(a[p], M1 - 2, M1));
t2.add(p, -powmod(a[p], M2 - 2, M2));
a[p] = x;
t1.add(p, powmod(a[p], M1 - 2, M1));
t2.add(p, powmod(a[p], M2 - 2, M2));
}
}
}
// 代码是 clay