fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define Fin          freopen("input.txt","r",stdin)
  5. #define Fout         freopen("output.txt","w",stdout)
  6.  
  7. const int mxN = 2e5 + 1;
  8. int ar[mxN];
  9. int seg[mxN << 2];
  10.  
  11. void Build(int cur, int left , int right) {
  12.     if (left == right) {
  13.         seg[cur] = ar[left];
  14.         return ;
  15.     }
  16.     int mid = (left + right) >> 1;
  17.     Build(cur << 1 , left , mid);
  18.     Build(cur << 1 | 1 , mid + 1 , right);
  19.     seg[cur] = __gcd(seg[cur << 1] , seg[cur << 1 | 1]);
  20. }
  21. int Query(int cur , int left , int right , int l , int r) {
  22.     if (right < l || r < left) return 0;
  23.     if (l <= left && right <= r) return seg[cur];
  24.     int mid = (left + right) >> 1;
  25.     int a = Query(cur << 1 , left , mid, l , r);
  26.     int b = Query(cur << 1 | 1 , mid + 1, right , l , r);
  27.     return __gcd(a , b);
  28. }
  29. void Update(int cur , int left , int right , int pos, int val) {
  30.     if (right < pos || pos < left) return;
  31.     if (pos <= left && right <= pos) {
  32.         seg[cur] = val;
  33.         ar[pos] = val;
  34.         return;
  35.     }
  36.     int mid = (left + right) >> 1;
  37.     Update(cur << 1, left , mid , pos , val);
  38.     Update(cur << 1 | 1 , mid + 1, right , pos , val);
  39.     seg[cur] = __gcd(seg[cur << 1] , seg[cur << 1 | 1]);
  40. }
  41. int main() {
  42.     ios_base::sync_with_stdio(0);
  43.     cin.tie(0);
  44.     cout.tie(0);
  45.     //Fin;
  46.     //Fout;
  47.     int n , q; cin >> n >> q;
  48.     for (int i = 1; i <= n; i++) cin >> ar[i];
  49.     Build(1 , 1 , n);
  50.     while (q--) {
  51.         int t; cin >> t;
  52.         if (t == 1) {
  53.             int k , u; cin >> k >> u;
  54.             Update(1 , 1 , n, k , u);
  55.         } else {
  56.             int l , r , x;
  57.             cin >> l >> r >> x;
  58.             cout << ((Query(1 ,1 , n , l , r) % x)? "No\n" : "Yes\n"); 
  59.         }
  60.     }
  61.     return 0;
  62. }
Success #stdin #stdout 0s 5452KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/vsasX2
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!