HackerEarth GCD problem solution

In this HackerEarth GCD problem solution, You are given an array of N integers. A function is defined as follows:

F(i,j) = G.C.C(Ai, Ai+1, ...Aj)

You are also given Q queries of the form L R. For every query, you must answer the value:

sigma(i=L,R) sigma(j=i+1, R) F(i,j)

HackerEarth GCD problem solution.

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

typedef long long ll;
const ll MAX = 200009;
const ll MAXlogN = 19;
ll ara[MAX];

ll A[MAX];
ll Log[MAX];
ll M[MAX][MAXlogN];

vector < pair < ll , ll > > perPos[MAX];

void buildSparse(ll n){
    for(ll i=1;i<=n;i++) M[i][0]=A[i];
    for(ll i=2;i<=n;i++) Log[i]=Log[i-1] + !(i&(i-1));

    for(ll j=1; (1<<j)<=n ;j++){
        for(ll i=1; (i+ (1<<j)-1) <=n; i++)
            M[i][j]=__gcd(M[i][j-1],M[i + (1<<(j-1))][j - 1]);
    }
}

ll Query(ll i,ll j){
    ll k=Log[j-i+1];
    return __gcd(M[i][k],M[j-(1<<k)+1][k]);
}

ll anss[MAX];

ll segtree[4 * MAX], lazy[4 * MAX];

void relax(ll node, ll beg, ll ed)
{
    segtree[node] += lazy[node] * (ed - beg + 1);
    if(beg != ed){
        lazy[2 * node] += lazy[node];
        lazy[2 * node + 1] += lazy[node];
    }
    lazy[node] = 0;
}

void update(ll node, ll beg, ll ed, ll i, ll j, ll val)
{
    if(lazy[node]) relax(node, beg, ed);
    if(beg > j || ed < i || beg > ed) return;
    if(beg >= i && ed <= j){
        lazy[node] += val;
        relax(node, beg, ed);
        return;
    }

    ll mid = (beg + ed) / 2;
    ll lft = 2 * node;
    ll rgh = lft + 1;

    update(lft, beg, mid, i, j, val);
    update(rgh, mid + 1, ed, i, j, val);

    segtree[node] = segtree[lft] + segtree[rgh];

}

ll query(ll node, ll beg, ll ed, ll i, ll j)
{
    if(lazy[node]) relax(node, beg, ed);
    if(beg > j || ed < i || beg > ed) return 0;
    if(beg >= i && ed <= j) return segtree[node];

    ll mid = (beg + ed) / 2;
    ll lft = 2 * node;
    ll rgh = lft + 1;

    ll p = query(lft, beg, mid, i, j);
    ll q = query(rgh, mid + 1, ed, i, j);

    return (p + q);
}

int main()
{
//    freopen("samplein01.txt", "r", stdin);
//    freopen("sampleout01.txt", "w", stdout);

    ll n, m;
    scanf("%lld %lld", &n, &m);

    for(ll i = 1; i <= n; i++){
        scanf("%lld", &ara[i]);
        A[i] = ara[i];
    }

    for(ll i = 1; i <= m; i++){
        ll L, R;
        scanf("%lld %lld", &L, &R);
        perPos[L].push_back({R, i});
    }

    buildSparse(n);

    for(ll i = n; i >= 1; i--){
        for(ll j = i; j <= n; ){
            ll lo = j, hi = n;

            ll nxt = lo;

            while(lo <= hi){
                ll mid = (lo + hi) / 2;
                if(Query(i, mid) == Query(i, j)){
                    nxt = mid;
                    lo = mid + 1;
                }
                else hi = mid - 1;
            }

            update(1, 1, n, j, nxt, Query(i, j));
            j = nxt + 1;

        }

        for(auto el : perPos[i]){
            ll l = i;
            ll r = el.first;
            ll id = el.second;

            anss[id] = query(1, 1, n, l, r);
        }

    }

    for(ll i = 1; i <= m; i++) printf("%lld\n", anss[i]);

    return 0;
}