Kazaee 题解

· · 题解

如果 a 出现在区间内出现次数是 x 且 x 是 k 的倍数，那么 x×b 显然也是 k 的倍数，其中 b 是任意一个值。

如果直接判断区间和是否是 k 的倍数，很显然会有许多反例，也会背卡。但是可以发现，随机数据的正确率是比较理想的。题中没有随机就可以创造随机。给每个数映射一个随机数值 w。如果把所有数都换成映射的数值，再直接判断区间和是否是 k 的倍数，正确率就能提高许多。

但是数据范围很大，还是有很大的概率出错。那就多映射几个。每个数都映射 T 个不同的随机值。如果在这 T 个映射表中，区间的和全都是 k 的倍数，那么满足条件的可能性就非常高。亲测 T 取 21 比较好。

但是如果暴力用 map，虽然复杂度没变，但是常数很大，不能通过。可以用一个 map 来进行离散化，然后用二维数组储存映射值。单点修改区间求和直接树状数组即可。T 取 21，复杂度 O(21n\log n)。有点卡常，加上快读快写即可。

#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ll long long
char *p1,*p2,buf[100000];
#define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
inline int read(){
    int x=0,f=1;
    char ch=nc();
    while(ch<48||ch>57)
    {
        if(ch=='-')
            f=-1;
        ch=nc();
    }
    while(ch>=48&&ch<=57)
        x=x*10+ch-48,ch=nc();
    return x*f;
}
inline ull randd(){
    return rand();
}
inline ull rands(){
    return ((randd()*randd()*randd()*randd()+randd())*randd()+randd())*randd()+randd();
}
int n,m,p[300005],mods=1e9+7,jd=21,f[35][600005],idx;
map<int,int>has;
struct tr{
    ll c[300005];
    void add(register int x,register int sum){
        while(x<=n){
            c[x]+=sum;
            x+=x&-x;
        }
    }
    ll gets(register int x){
        ll sum=0;
        while(x){
            sum+=c[x];
            x-=x&-x;
        }
        return sum;
    }
}q[26];
inline void sets(int x,int y){
    if(has.find(y)==has.end()){
        has[y]=++idx;
        for(int i=1;i<=jd;i++){
            f[i][idx]=rands()%mods;
        }
    }
    int c=has[p[x]],cc=has[y];
    for(int i=1;i<=jd;i++){
        q[i].add(x,-f[i][c]);
        q[i].add(x,f[i][cc]);
    }
    p[x]=y;
}
inline bool solve(int l,int r,int k){
    for(register int i=1;i<=jd;i++){
        if((q[i].gets(r)-q[i].gets(l-1))%k)return 0;
    }
    return 1;
}
signed main(){
    srand(time(NULL));
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        p[i]=read();
        if(has.find(p[i])==has.end()){
            has[p[i]]=++idx;
            for(int j=1;j<=jd;j++){
                f[j][idx]=rands()%mods;
            }
        }
        int c=has[p[i]];
        for(int j=1;j<=jd;j++){
            q[j].add(i,f[j][c]);
        }
    }
    while(m--){
        int op,x,y,z;
        op=read(),x=read(),y=read();
        if(op==1){
            sets(x,y);
        }else{
            z=read();
            if(solve(x,y,z))printf("YES\n");
            else printf("NO\n");
        }
    }
}