如题，思路就是正常的跑 $30$ 次随机化验证，但是为什么我第三个点就 TLE 了啊，有没有大佬可以看下是实现得太丑了还是有地方写挂了。

#include<bits/stdc++.h>
#define fi first
#define se second
#define Mp make_pair
#define pb emplace_back
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rof(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int N=1e6+5;
const int mod=1e9+7;
const int inf=1e9;
struct Query{
    int opt,i,x;
    int l,r,k;
}q[N];
int n,m,tot,a[N],t[N],b[N],w[N];
ll c[N];
bool ans[N];
int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
    return x*f;
}
int randint(int l,int r){
    mt19937_64 lmt;
    lmt.seed(rand());
    return l+lmt()%(r-l);
}
int lowbit(int x){return x&(-x);}
void add(int x,int y){for(;x<=n;x+=lowbit(x))c[x]+=y;}
ll query(int x){ll res=0;for(;x;x-=lowbit(x))res+=c[x];return res;}
ll query(int l,int r){return query(r)-query(l-1);}
int Hash(int x){return lower_bound(b+1,b+tot+1,x)-b;}
void init(){
    sort(b+1,b+tot+1);
    memset(ans,1,sizeof(ans));
    tot=unique(b+1,b+tot+1)-b-1;
    For(i,1,n) a[i]=Hash(a[i]);
    For(i,1,m) if(q[i].opt==1) q[i].x=Hash(q[i].x);
}
void work(){
    memset(c,0,sizeof(c));
    For(i,1,tot) w[i]=randint(1,1e9);
    For(i,1,n) t[i]=a[i],add(i,w[t[i]]);
    For(i,1,m){
        if(q[i].opt==1){
            add(q[i].i,w[q[i].x]-w[t[q[i].i]]);
            t[q[i].i]=q[i].x;
        }
        else{
            ll sum=query(q[i].l,q[i].r);
            if(sum%q[i].k) ans[i]=0;
        }
    }
}
void Main(){
    n=read();m=read();
    For(i,1,n) a[i]=read(),b[++tot]=a[i];
    For(i,1,m){
        q[i].opt=read();
        if(q[i].opt==1){
            q[i].i=read();q[i].x=read();
            b[++tot]=q[i].x;
        }
        else q[i].l=read(),q[i].r=read(),q[i].k=read();
    }
    init();int T=30;
    while(T--) work();
    For(i,1,m) if(q[i].opt==2) puts(ans[i]?"YES":"NO");
}
signed main(){
    int T=1;//cin>>T;
    srand(time(0));
    while(T--) Main();
    return 0;
}