CF1746F Kazaee 题解

fanypcd · 2022-11-05 16:53:06 · 题解

Kazaee

给出一个长度为 n 的数组 a 和以下两种操作：

碰到这种常见数据结构几乎不可做的，但是又感觉很简单的操作，考虑随机化。

随机地将 a_i 映射到值域内的另一个数上 （a_i \to b_i），考虑询问操作 [l,r]，求出 S=\sum \limits_{i=l}^r b_i，显然如果 k \nmid S 一定是 NO，但是 k \mid S 不一定真的是 YES。

我们考虑一下错判 NO 为 YES 的概率：

• 假设存在一个数 x \to y （映射后的值是 y）在区间中的出现次数 cnt_x，且 k \nmid cnt_x 但 k \mid y \times cnt_x，这近似要求 k \mid y，所以错误率大概是 1 \over k。

• 还有一种理解方式：S=\sum \limits_{x~\text{exists in}~a[l,r]}cnt_x \times y，其中 y 是完全随机的，那么可以认为 S 也是随机的，所以在错误情况中，存在一个随机的 S 满足 k \mid S 的概率近似认为是 1 \over k。

然后就可以用树状数组维护前缀和，多随机映射几次，直到错误的概率小到可以接受即可水过此题。

#include<bits/stdc++.h>
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int f = 0; char ch = getchar();
    while(ch < '0' || ch > '9')
        f |= ch == '-', ch = getchar();
    while('0' <= ch && ch <= '9')
        x = x * 10 + ch - 48, ch = getchar();
    x = f ? -x : x; return;
}
#define inf 0x3f3f3f3f
#define ll long long
#define fir first
#define sec second
#define N 300005
int n, Q, a[N], b[N];
mt19937 rnd(time(0));
#define lowbit(x) (x & -x)
ll val[N];
inline void update(int p, int v) {
    while(p <= n) {
        val[p] += v;
        p += lowbit(p);
    }
    return;
}
inline ll qry(int p) {
    ll res = 0; while(p) {
        res += val[p];
        p -= lowbit(p);
    }
    return res;
}
inline ll qry(int L, int R) {
    return qry(R) - qry(L - 1);
}
int op[N], l[N], r[N], k[N];
int num[N << 1], ntot;
int Ref[N << 1];
int ans[N];
signed main() {
    read(n), read(Q);
    for(int i = 1; i <= n; i++) read(a[i]), num[++ntot] = a[i];
    for(int i = 1; i <= Q; i++) {
        read(op[i]), read(l[i]), read(r[i]);
        ans[i] = 1;
        if(op[i] == 2) read(k[i]);
        else num[++ntot] = r[i];
    }
    sort(num + 1, num + ntot + 1);
    ntot = unique(num + 1, num + ntot + 1) - num - 1;
    for(int i = 1; i <= n; i++) {
        a[i] = lower_bound(num + 1, num + ntot + 1, a[i]) - num;
    }
    for(int i = 1; i <= Q; i++) {
        if(op[i] == 1) {
            r[i] = lower_bound(num + 1, num + ntot + 1, r[i]) - num;
        }
    }
    for(int T = 1; T <= 30; T++) {
        memset(val, 0, sizeof(val));
        memcpy(b, a, sizeof(b));
        for(int i = 1; i <= ntot; i++) {
            Ref[i] = rnd() >> 1;
        }
        for(int i = 1; i <= n; i++) {
            update(i, Ref[b[i]]);
        }
        for(int i = 1; i <= Q; i++) {
            if(op[i] == 1) {
                update(l[i], Ref[r[i]] - Ref[b[l[i]]]);
                b[l[i]] = r[i];
            }
            else {
                if(ans[i]) {
                    if((r[i] - l[i] + 1) % k[i]) {
                        ans[i] = 0; continue;
                    }
                    if(qry(l[i], r[i]) % k[i]) {
                        ans[i] = 0; continue;
                    }
                }
            }
        }
    }
    for(int i = 1; i <= Q; i++) {
        if(op[i] == 2) {
            if(ans[i]) puts("YES");
            else puts("NO");
        }
    }
    return 0;
}