In this HackerEarth Greatest common divisor problem solution, you are given array A. There are 4 types of operations associated with it:
  1. l r x, for each i ∈ [l, r] replace ai with the value of x.
  2. l r x, for each i ∈ [l, r] replace ai with the value of the gcd(ai, x) function.
  3. l r, print the value of max ai, l ≤ i ≤ r.
  4. l r, print the value of al + al+1 + ... + ar.
The greatest common divisor (gcd(a, b)) of two positive integers a and b is equal to the biggest integer d such that both integers a and b are divisible by d.


HackerEarth Greatest common divisor problem solution


HackerEarth Greatest common divisor problem solution.

#include<bits/stdc++.h>
using namespace std;

const int MAX_N = 2e5 + 111;

struct node{
long long sum;
int element;
int mx;
int lz;
int l, r;

node(){
element = -1;
sum = 0;
mx = 0;
lz = -1;
l = 0;
r = 0;
}

node(int value){
element = value;
sum = value;
mx = value;
}

};

node t[4 * MAX_N];
int a[MAX_N];
int n, q;

inline node merge(node a, node b){
node c = node();

c.sum = a.sum + b.sum;

c.mx = max(a.mx, b.mx);
if(a.element == b.element && a.element > 0)
c.element = a.element; else c.element = -1;

return c;
}

void build(int v,int tl,int tr){
if(tl == tr){
t[v] = node(a[tl]);
t[v].l = t[v].r = tl;
return;
}
int tm = (tl + tr) >> 1,
L = v << 1,
R = L | 1;
build(L, tl, tm);
build(R, tm + 1, tr);
t[v] = merge(t[L],t[R]);
t[v].l = tl;
t[v].r = tr;
}

inline void assignment(int v,int val){
t[v].lz = val;
t[v].sum = (t[v].r - t[v].l + 1) *1ll* val;
t[v].mx = val;
t[v].element = val;
}

inline void push(int v,int L,int R){
if(t[v].lz != -1){
if(t[v].l != t[v].r){
assignment(L, t[v].lz);
assignment(R, t[v].lz);
int l = t[v].l,
r = t[v].r;
t[v] = merge(t[L],t[R]);
t[v].l = l;
t[v].r = r;
}
t[v].lz = -1;
}
}

void update1(int v,int l,int r,int val){
if(t[v].l > r || t[v].r < l)return;
if(t[v].l >= l && t[v].r <= r){
assignment(v, val);
return;
}
int L = v << 1,
R = L | 1;
push(v, L, R);
update1(L, l, r, val);
update1(R, l, r, val);
int l_ = t[v].l,
r_ = t[v].r;
t[v] = merge(t[L], t[R]);
t[v].l = l_;
t[v].r = r_;
}

void update2(int v,int l,int r,int val){
if(t[v].l > r || t[v].r < l)return;
if(t[v].l >= l && t[v].r <= r && t[v].element > 0){
assignment(v, __gcd(val, t[v].element));
return;
}
int L = v << 1,
R = L | 1;
push(v, L, R);
update2(L, l, r, val);
update2(R, l, r, val);
int l_ = t[v].l,
r_ = t[v].r;
t[v] = merge(t[L], t[R]);
t[v].l = l_;
t[v].r = r_;
}

node NULL_;

node get(int v,int l,int r){
if(t[v].l > r || t[v].r < l)return NULL_;
int L = v << 1,
R = L | 1;
push(v, L, R);
if(t[v].l >= l && t[v].r <= r)return t[v];
int tm = (t[v].l + t[v].r) >> 1;
if(r <= tm)return get(L, l, r);
if(l > tm)return get(R, l, r);
node ans1 = get(L, l, r),
ans2 = get(R, l, r);
node ans = merge(ans1, ans2);
return ans;
}

int main(){

ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

// freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);

int n, q;
cin >> n >> q;
for(int i = 1; i <= n; ++i){
cin >> a[i];
}

build(1, 1, n);

while(q-->0){
int type, l, r;
cin >> type >> l >> r;
if(type == 1){
int x;
cin >> x;
update1(1, l, r, x);
}else
if(type == 2)
{
int x;
cin >> x;
update2(1, l, r, x);
}else{
if(type == 3)cout << get(1, l, r).mx << '\n';
else cout << get(1, l, r).sum << '\n';
}
}

return 0;
}