fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. vector<int> tree;
  6. int n;
  7.  
  8. int gcd (int a, int b){
  9.     if (a == 0) return b;
  10.    return gcd(b % a, a);
  11. }
  12. void build(int a[], int v = 1, int tl = 0, int tr = n - 1){
  13.     if(tl == tr){
  14.         tree[v] = a[tl];
  15.     }else{
  16.         int middle = (tl + tr) / 2;
  17.         build(a, v * 2, tl, middle);
  18.         build(a, v * 2 + 1, middle + 1, tr);
  19.         tree[v] = gcd(tree[v * 2], tree[v * 2 + 1]);
  20.     }
  21. }
  22.  
  23. int get(int a[], int l, int r, int v = 1, int tl = 0, int tr = n-1){
  24.     if(l > r){
  25.         return 0;
  26.     }
  27.     if(tl == l && tr == r){
  28.         return tree[v];
  29.     }
  30.     int middle = (tl + tr) / 2;
  31.     int L = get(a, l, min(middle, r), v * 2, tl, middle);
  32.     int R = get(a, max(middle + 1, l), r, v*2 + 1, middle + 1, tr);
  33.     return gcd(L, R);
  34. }
  35. void update(int pos, int val, int v = 1, int tl = 0, int tr = n - 1){
  36.     if(tl == tr){
  37.         tree[v] = val;
  38.     }else{
  39.         int middle = (tl + tr) / 2;
  40.         if(pos <= middle){
  41.             update(pos, val, v * 2, tl, middle);
  42.         }else{
  43.             update(pos, val, v * 2 + 1, middle + 1, tr);
  44.         }
  45.         tree[v] = gcd(tree[v * 2], tree[v * 2 + 1]);
  46.     }
  47. }
  48.  
  49. int main(){
  50.     cin >> n;
  51.     int a[n];
  52.     for (int i = 0; i < n; i++){
  53.         cin >> a[i];
  54.     }
  55.     tree.resize(4 * n);
  56.     build(a);
  57.     int m, l, r, q; 
  58.     cin >> m;
  59.     while (m--){
  60.         cin >> q >> l >> r;
  61.         if (q == 1){
  62.             cout << get(a, l - 1, r - 1) << endl;
  63.         }
  64.         else{
  65.         	update(l - 1, r);
  66.         }
  67.     }
  68.     return 0;
  69. }
Success #stdin #stdout 0s 3464KB
comments (?)
stdin
copy 
5
2 4 6 10 8
6
1 1 5
1 2 3
2 5 15
2 3 10
1 3 5
1 1 5
stdout
copy 
2
2
5
1
https://ideone.com/CjzMjU
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!