发现直接维护区间内每个数的出现次数并不好做。不妨把这个条件外推，假设 \([l,r]\) 中每个数的出现次数都是 \(k\) 的倍数，那么 \(\sum_{i=l}^r a_i\) 也是 \(k\) 的倍数，即后者是前者的必要条件，并且当 \(a_i\) 较大时，后者成立时前者成立的概率会越大。
因此我们可以这样判定：如果 \(\sum_{i=l}^r a_i\) 是 \(k\) 的倍数，那么 \([l,r]\) 中每个数的出现次数都是 \(k\) 的倍数。当然，在此之前，我们要对 \(a_i\)（以及修改的值）进行随机替换（只需确保原本相同的数替换后仍相同），从而提高判定正确率。判定需要进行一定的次数，我取了 \(30\) 次。初始时假定都是成立的，一旦有一次判定不成立即为不成立。若干次以后，错误率已经极低了，基本可以忽略。
于是用树状数组维护序列即可。随机时可以使用 mt19937 以增大随机数的分布范围。
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#define int long long
#define N 1000001using namespace std;mt19937 rnd( time( NULL ) );struct Q
{int op,l,r,k,x,y,flag;
}q[N];int n,a[N],b[N],c[N],d[N],f[N],t[N],tot,m;int lowbit( int x )
{return x & ( -x );
}void upd( int x , int y )
{for( int i = x ; i <= n ; i += lowbit( i ) )t[i] += y;return;
}int que( int x )
{int sum = 0;for( int i = x ; i >= 1 ; i -= lowbit( i ) )sum += t[i];return sum;
}signed main()
{ios::sync_with_stdio( false );cin.tie( 0 );cout.tie( 0 );cin >> n >> m;for( int i = 1 ; i <= n ; i ++ )cin >> a[i],c[++ tot] = a[i];for( int i = 1 ; i <= m ; i ++ ){cin >> q[i].op;if( q[i].op == 1 )cin >> q[i].x >> q[i].y,c[++ tot] = q[i].y;if( q[i].op == 2 )cin >> q[i].l >> q[i].r >> q[i].k,q[i].flag = 1;}sort( c + 1 , c + tot + 1 );tot = unique( c + 1 , c + tot + 1 ) - c - 1;for( int i = 1 ; i <= n ; i ++ )a[i] = lower_bound( c + 1 , c + tot + 1 , a[i] ) - c;for( int i = 1 ; i <= m ; i ++ )if( q[i].op == 1 )q[i].y = lower_bound( c + 1 , c + tot + 1 , q[i].y ) - c;int T = 30;while( T -- ){for( int i = 1 ; i <= tot ; i ++ )b[i] = rnd() % 1000000007 + 1;for( int i = 1 ; i <= n ; i ++ )t[i] = 0;for( int i = 1 ; i <= n ; i ++ )upd( i , b[a[i]] ),f[i] = a[i];for( int i = 1 ; i <= m ; i ++ ){if( q[i].op == 1 ) upd( q[i].x , b[q[i].y] - b[f[q[i].x]] ),f[q[i].x] = q[i].y;if( q[i].op == 2 ){if( ( que( q[i].r ) - que( q[i].l - 1 ) ) % q[i].k )q[i].flag = 0;}}}for( int i = 1 ; i <= m ; i ++ )if( q[i].op == 2 ){if( q[i].flag ) cout << "YES\n";else cout << "NO\n";}return 0;
}